A tree--arrowing graph

1997/08/15 by E. C. Milner, Eric C. Milner, Saharon Shelah +2
Computer Science · Mathematics · #Advanced Graph Theory Research #FOS: Mathematics #Logic (math.LO) #math.LO

paper · pdf · doi:10.48550/arxiv.math/9708210

published as in: {Set theory (Curac{c}ao, 1995; Barcelona, 1996)} (1998) 175--182

arxiv created 1997/08/15 · openalex publication_date 1997/08/15 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We answer a variant of a question of Rodl and Voigt by showing that, for a given infinite cardinal lambda, there is a graph G of cardinality kappa =(2^lambda)⁺ such that for any colouring of the edges of G with lambda colours, there is an induced copy of the kappa-tree in G in the set theoretic sense with all edges having the same colour.

Related

• A Note on Edge Colorings and Trees
• An application of CAT
• A note on total and list edge-colouring of graphs of tree-width 3
• The colouring number of infinite graphs
• Repeated patterns in proper colourings