Dirac's conjecture was proved, for $k=5$: There exists a graph $G$ with chromatic number $5$, such
that every vertex is critical, yet every critical set of edges has size $>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
Actions
Submit a Proof
Have a proof attempt? Submit it for zero-trust verification.
