Erdős Problem #626 — Let k≥4k\geq 4 and gk(n)g_k(n) denote the largest mm such that there is a graph on nn vertices with chromatic number kk and girth >m>m (i.

About 67 years old · traced to

Let k≥4k\geq 4 and gk(n)g_k(n) denote the largest mm such that there is a graph on nn vertices with chromatic number kk and girth >m>m (i.e. contains no cycle of length ≤m\leq m). Does lim⁡n→∞gk(n)log⁡n\lim_{n\to \infty}\frac{g_k(n)}{\log n} exist? Conversely, if h(m)(n)h^{(m)}(n) is the maximal chromatic number of a graph on nn vertices with girth >m>m then does lim⁡n→∞log⁡h(m)(n)log⁡n\lim_{n\to \infty}\frac{\log h^{(m)}(n)}{\log n} exist, and what is its value?

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.