← All problems

Erdős Problem #921 — Longest possible odd girth at fixed chromatic number

57 years old · traced to

For integers k≥4k\ge 4 and n≥kn\ge k, let fk(n)f_k(n) be the largest integer mm for which there is a graph GG on nn vertices with chromatic number χ(G)=k\chi(G)=k and every odd cycle in GG has length greater than mm. Cycle length is measured in edges. Equivalently, fk(n)f_k(n) is the largest odd girth attainable by an nn-vertex kk-chromatic graph, minus one. The question is whether, for each fixed k≥4k\ge4, there are constants ck,Ck>0c_k,C_k>0 and an integer n0(k)n_0(k) such that for every n≥n0(k)n\ge n_0(k),

ckn1/(k−2)≤fk(n)≤Ckn1/(k−2).c_k n^{1/(k-2)}\le f_k(n)\le C_k n^{1/(k-2)}.

Erdős Problem #921 Erdős (1969)

Background

Erdős presented the question as a conjecture of Gallai and himself. In his 1969 account, he contrasted general results bounding chromatic number when short cycles are forbidden with the more delicate issue of forbidding short odd cycles: Gallai had constructed a four-chromatic graph whose shortest odd cycle has length greater than a constant multiple of n1/2n^{1/2}. This showed why a logarithmic odd-cycle threshold cannot force three-colorability and suggested the exponent 1/(k−2)1/(k-2) for higher fixed chromatic numbers. Erdős (1969) Erdős Problem #921

References

P. Erdős, Problems and results in chromatic graph theory, in Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., 1968), Academic Press (1969), 27–35.

Source: P. Erdős, Problems and results in chromatic graph theory, in Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., 1968), Academic Press (1969), 27–35.

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.