Skip to content

Erdős problem 628

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 statement2 of 4

Balogh, Kostochka, Prince, and Stiebitz [BKPS09] proved the conjecture for graphs with independence number 2.

FormalConjectures/ErdosProblems/628.leanErdos628.erdos_628.variants.independence_number_210 linesExact file
∀ (V : Type u_1) [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj],  G.indepNum = 2 →    ∀ (k : ℕ),      G.chromaticNumber = ↑k →        G.CliqueFree k →          ∀ (a b : ℕ),            a ≥ 2 →              b ≥ 2 →                a + b = k + 1 →                  ∃ s, (SimpleGraph.induce s G).chromaticNumber ≥ ↑a ∧ (SimpleGraph.induce sᶜ G).chromaticNumber ≥ ↑b
SolvedStatement only, no proof