Erdős problem 628 · problems.science

Let $G$ be a graph with chromatic number $k$ containing no $K_k$ . If $a,b\geq 2$ and $a+b=k+1$ then must there exist two disjoint subgraphs of $G$ with chromatic numbers $\geq a$ and $\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 statement4 of 4

Balogh, Kostochka, Prince, and Stiebitz [BKPS09] proved the conjecture for quasi-line graphs.

FormalConjectures/ErdosProblems/628.leanErdos628.erdos_628.variants.quasi_line10 linesExact file

1∀ (V : Type u_1) [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj],2  G.IsQuasiLineGraph →3    ∀ (k : ℕ),4      G.chromaticNumber = ↑k →5        G.CliqueFree k →6          ∀ (a b : ℕ),7            a ≥ 2 →8              b ≥ 2 →9                a + b = k + 1 →10                  ∃ s, (SimpleGraph.induce s G).chromaticNumber ≥ ↑a ∧ (SimpleGraph.induce sᶜ G).chromaticNumber ≥ ↑b

SolvedStatement only, no proof

Sources

Search problems.science