Erdős Problem #921 — Longest possible odd girth at fixed chromatic number
For integers and , let be the largest integer for which there is a graph on vertices with chromatic number and every odd cycle in has length greater than . Cycle length is measured in edges. Equivalently, is the largest odd girth attainable by an -vertex -chromatic graph, minus one. The question is whether, for each fixed , there are constants and an integer such that for every ,
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 . This showed why a logarithmic odd-cycle threshold cannot force three-colorability and suggested the exponent 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.
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.