Skip to content

Erdős problem 751

Let GG be a graph with chromatic number χ(G)=4\chi(G)=4. If m1<m2<m_1<m_2<\cdots are the lengths of the cycles in GG then can min(mi+1mi)\min(m_{i+1}-m_i) be arbitrarily large? Can this happen if the girth of GG is large?

Sources

Browse retained paths and inspect the exact material available for this Problem.

3 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

751.lean

Retained formal statement2 of 3

Let GG be a graph with chromatic number χ(G)=4\chi(G)=4. If m1<m2<m_1<m_2<\cdots are the lengths of the cycles in GG then can min(mi+1mi)\min(m_{i+1}-m_i) be arbitrarily large? Can this happen if the girth of GG is large?

The answer is no: Bondy and Vince [BoVi98] proved that every graph with minimum degree at least 33 has two cycles whose lengths differ by at most 22, and hence the same is true for every graph with chromatic number 44.

FormalConjectures/ErdosProblems/751.leanErdos751.erdos_751.parts.ii3 linesExact file
False  ∀ (k g : ℕ),V G, G.chromaticNumber = 4 ∧ gG.girth ∧ ∀ mG.cycleLengths, ∀ m'G.cycleLengths, m < m'm + km'
SolvedStatement only, no proof

Search problems.science

Find a Problem, Result, source, or page