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?

No current result

No reviewed Result is current in Vela Mathematics Program. Retained source material is shown below.

Retained declaration

FormalConjectures/ErdosProblems/628.lean

Formal Conjectures

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

Continue

Start a contributionBrowse the source filesOpen the collection entry

Search problems.science

Find a Problem, Result, source, or page