Skip to content

Erdős problem 751

Start work

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+1−mi)\min(m_{i+1}-m_i) be arbitrarily large? Can this happen if the girth of GG is large?

Sources

The source's own material, retained exactly.

3 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

751.lean

Retained formal statement3 of 3

Bondy and Vince [BoVi98] proved that every graph with minimum degree at least 33 has two cycles whose lengths differ by at most 22.

FormalConjectures/ErdosProblems/751.leanErdos751.erdos_751.variants.bondy_vince2 linesExact file
∀ {V : Type u_1} [inst : Fintype V] (G : SimpleGraph V) [inst_1 : DecidableRel G.Adj],  3 ≤ G.minDegree → ∃ m ∈ G.cycleLengths, ∃ m' ∈ G.cycleLengths, m < m' ∧ m' ≤ m + 2
SolvedStatement only, no proof