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

Erdős [Er68b] originally asked about $a=b=3$ which was proved by Brown and Jung [BrJu69] (who in fact prove that $G$ must contain two vertex disjoint odd cycles)..

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

1∀ (V : Type u_1) [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj],2  G.chromaticNumber = 5 →3    G.CliqueFree 5 → ∃ s, (SimpleGraph.induce s G).chromaticNumber ≥ 3 ∧ (SimpleGraph.induce sᶜ G).chromaticNumber ≥ 3

SolvedStatement only, no proof

Sources

Search problems.science