Skip to content

Erdős problem 628

Start work

Let GG be a graph with chromatic number kk containing no KkK_k. If a,b≥2a,b\geq 2 and a+b=k+1a+b=k+1 then must there exist two disjoint subgraphs of GG with chromatic numbers ≥a\geq a and ≥b\geq b respectively?

Sources

The source's own material, retained exactly.

4 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

628.lean

Retained formal statement3 of 4

Erdős [Er68b] originally asked about a=b=3a=b=3 which was proved by Brown and Jung [BrJu69] (who in fact prove that GG must contain two vertex disjoint odd cycles)..

FormalConjectures/ErdosProblems/628.leanErdos628.erdos_628.variants.k_5_a_3_b_33 linesExact file
∀ (V : Type u_1) [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj],  G.chromaticNumber = 5 →    G.CliqueFree 5 → ∃ s, (SimpleGraph.induce s G).chromaticNumber ≥ 3 ∧ (SimpleGraph.induce sᶜ G).chromaticNumber ≥ 3
SolvedStatement only, no proof