Erdős Problem #626 — Chromatic graphs with large girth
Let be a finite graph, let denote its number of vertices, let be its chromatic number, and let be the length of its shortest cycle (taken as if it has no cycles). For each fixed integer and all sufficiently large integers , define
Thus the condition excludes every cycle of length at most . For each fixed positive integer , define
The questions are, first, whether for every fixed the limit exists and, second, whether for every fixed positive integer the limit exists and, if it does, what its value is. The choice of logarithm base does not affect either ratio. The first maximum is defined for all sufficiently large by the existence of graphs of arbitrarily large girth and chromatic number at least , together with passage to a subgraph of chromatic number and addition of isolated vertices. [Erdős Problem #626; Nešetřil, A combinatorial classic - sparse graphs with high chromatic number] Erdős Problem #626 Nešetřil, A combinatorial classic - sparse graphs with high chromatic number
Background
The underlying phenomenon is that forbidding short cycles does not force a graph to have low chromatic number: graphs can be locally sparse while remaining globally difficult to color. Erdős proved the arbitrary-girth, high-chromatic-number existence theorem in work from 1958, published as “Graph theory and probability” in 1959. Its probabilistic method takes a sparse random graph with a small independence number and removes edges lying in short cycles; the remaining graph still has high chromatic number while having no short cycles. This construction also gives quantitative control on the tradeoff between order, girth, and chromatic number. [Erdős, “Graph theory and probability”; Nešetřil, A combinatorial classic - sparse graphs with high chromatic number] Nešetřil, A combinatorial classic - sparse graphs with high chromatic number Erdős, Graph theory and probability (1959)
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.