Erdős problem 751 · problems.science

Let $G$ be a graph with chromatic number $\chi(G)=4$ . If $m_1<m_2<\cdots$ are the lengths of the cycles in $G$ then can $\min(m_{i+1}-m_i)$ be arbitrarily large? Can this happen if the girth of $G$ 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 statement1 of 3

Let $G$ be a graph with chromatic number $\chi(G)=4$ . If $m_1<m_2<\cdots$ are the lengths of the cycles in $G$ then can $\min(m_{i+1}-m_i)$ be arbitrarily large?

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

FormalConjectures/ErdosProblems/751.leanErdos751.erdos_751.parts.i1 lineExact file

1False ↔ ∀ (k : ℕ), ∃ V G, G.chromaticNumber = 4 ∧ ∀ m ∈ G.cycleLengths, ∀ m' ∈ G.cycleLengths, m < m' → m + k ≤ m'

SolvedStatement only, no proof

Sources

Search problems.science