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

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?

FormalConjectures/ErdosProblems/628.leanErdos628.erdos_6288 linesExact file
∀ (V : Type u_1) [Fintype V] (G : SimpleGraph V) (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
OpenStatement only, no proof