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

Dirac's conjecture was proved, for k=5k=5: There exists a graph GG with chromatic number 55, such that every vertex is critical, yet every critical set of edges has size >1>1, or in other words: has no critical edge.

[Br92] Brown, Jason I., A vertex critical graph without critical edges. Discrete Math. (1992), 99--101

FormalConjectures/ErdosProblems/944.leanErdos944.erdos_944.variants.dirac_conjecture.k_eq_51 lineExact file
∃ V G, Erdos944.SimpleGraph.IsErdos944 G 5 1
SolvedStatement only, no proof