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

Browse retained paths and inspect the exact material available for this Problem.

4 retained statements2415f78e850a

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

Search problems.science

Find a Problem, Result, source, or page