Triangle-free subgraphs of large chromatic number

DefinitionErdős Problem 923 on triangle-free subgraphs of large chromatic number#✓fully proved

The proposition asserts that for every natural number \(n\) there is a natural number \(k\) such that every simple graph \(G\), on any vertex set, whose chromatic number is at least \(k\) has a triangle-free subgraph \(H\) on the same vertex set whose chromatic number is at least \(n\). Chromatic numbers may be infinite.

def conjecture : Prop :=
  ∀ n : ℕ, ∃ k : ℕ, ∀ (V : Type*) (G : SimpleGraph V),
    (k : ℕ∞) ≤ G.chromaticNumber →
      ∃ H ≤ G, (n : ℕ∞) ≤ H.chromaticNumber ∧ H.CliqueFree 3

Used by 1

Used byRödl's theorem on triangle-free subgraphs

TheoremRödl's theorem on triangle-free subgraphs#●ready to prove

For every natural number \(n\) there is a natural number \(k\) such that every simple graph \(G\), on any vertex set, whose chromatic number is at least \(k\) has a triangle-free subgraph \(H\) on the same vertex set whose chromatic number is at least \(n\). Chromatic numbers may be infinite.

This answers Erdős Problem 923 affirmatively; it was proved by Rödl.

public theorem_wanted conjecture_holds : conjecture

Sources

• Vojtěch Rödl, On the chromatic number of subgraphs of a given graph, Proceedings of the American Mathematical Society 64 (1977), 370–371, https://doi.org/10.1090/S0002-9939-1977-0469806-4.

Uses 1

Statement usesErdős Problem 923 on triangle-free subgraphs of large chromatic number

1 fully proved1 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.