← All problems

Erdős Problem #626 — Chromatic graphs with large girth

67 years old · traced to

Let GG be a finite graph, let ∣V(G)∣|V(G)| denote its number of vertices, let χ(G)\chi(G) be its chromatic number, and let girth⁡(G)\operatorname{girth}(G) be the length of its shortest cycle (taken as ∞\infty if it has no cycles). For each fixed integer k≥4k\ge 4 and all sufficiently large integers nn, define

gk(n)=max⁡{m∈Z≥0:∣V(G)∣=n, χ(G)=k, girth⁡(G)>m for some G}.g_k(n)=\max\{m\in\mathbb Z_{\ge 0}: |V(G)|=n,\ \chi(G)=k,\ \operatorname{girth}(G)>m\text{ for some }G\}.

Thus the condition girth⁡(G)>m\operatorname{girth}(G)>m excludes every cycle of length at most mm. For each fixed positive integer mm, define

h(m)(n)=max⁡{χ(G):∣V(G)∣=n, girth⁡(G)>m}.h^{(m)}(n)=\max\{\chi(G): |V(G)|=n,\ \operatorname{girth}(G)>m\}.

The questions are, first, whether for every fixed k≥4k\ge4 the limit lim⁡n→∞gk(n)/log⁡n\lim_{n\to\infty}g_k(n)/\log n exists and, second, whether for every fixed positive integer mm the limit lim⁡n→∞log⁡h(m)(n)/log⁡n\lim_{n\to\infty}\log h^{(m)}(n)/\log n 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 nn by the existence of graphs of arbitrarily large girth and chromatic number at least kk, together with passage to a subgraph of chromatic number kk 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

Progress summary

Never refreshed

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.