Skip to content

Erdős problem 944

Let k≥4k \ge 4 and r≥1r\ge 1. Must there exist a graph GG with chromatic number kk such that every vertex is critical, yet every critical set of edges has size >r>r?

Sources

The source's own material, retained exactly.

7 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

944.lean

Retained formal statement6 of 7

Lattanzio [La02] proved there exist kk-critical graphs without critical edges for all kk such that k−1k - 1 is not prime.

[La02] Lattanzio, John J., A note on a conjecture of {D}irac. Discrete Math. (2002), 323--330

FormalConjectures/ErdosProblems/944.leanErdos944.erdos_944.variants.dirac_conjecture.k_sub_one_not_prime1 lineExact file
∀ (k : ℕ), 4 ≤ k → ¬Nat.Prime (k - 1) → ∃ V G, Erdos944.SimpleGraph.IsErdos944 G k 1
SolvedStatement only, no proof