Erdős problem 944

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

Sources

The source's own material, retained exactly.

7 retained statements36c6d0fef71a

FormalConjectures/ErdosProblems/

944.lean

Retained formal statement5 of 7

Jensen [Je02] gave an construction for $k$ -critical graphs without any critical edges for all $k ≥ 5$ .

[Je02] Jensen, Tommy R., Dense critical and vertex-critical graphs. Discrete Math. (2002), 63--84.

FormalConjectures/ErdosProblems/944.leanErdos944.erdos_944.variants.dirac_conjecture.k_ge_five1 lineExact file

1∀ (k : ℕ), 5 ≤ k → ∃ V G, Erdos944.SimpleGraph.IsErdos944 G k 1

SolvedStatement only, no proof