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 statement3 of 3

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

FormalConjectures/ErdosProblems/751.leanErdos751.erdos_751.variants.bondy_vince2 linesExact file

1∀ {V : Type u_1} [inst : Fintype V] (G : SimpleGraph V) [inst_1 : DecidableRel G.Adj],2  3 ≤ G.minDegree → ∃ m ∈ G.cycleLengths, ∃ m' ∈ G.cycleLengths, m < m' ∧ m' ≤ m + 2

SolvedStatement only, no proof

Sources

Search problems.science