Draft:Dirac's critical-graph conjecture

Dirac's critical-graph conjecture is an open problem in graph theory concerning the difference between vertex-critical and edge-critical graphs. It asks whether, for every integer $k\geq 4$, there is a graph whose chromatic number is $k$, whose chromatic number falls when any vertex is deleted, but whose chromatic number does not fall when any single edge is deleted. The conjecture is known for every $k\geq 5$; the remaining case is $k=4$.

Definitions and statement

For a graph $G$, let $\chi (G)$ denote its chromatic number. A graph is $k$-vertex-critical if

• $\chi (G)=k$; and
• $\chi (G-v)=k-1$ for every vertex $v$ of $G$.

An edge $e$ is critical if $\chi (G-e)<\chi (G)$. In this terminology, Dirac's conjecture states:

For every integer $k\geq 4$, there exists a $k$-vertex-critical graph having no critical edge.

Equivalently, the unresolved $k=4$ case asks for a graph $G$ such that

$$\chi (G)=4,\qquad \chi (G-v)=3{\text{ for every }}v\in V(G),\qquad \chi (G-e)=4{\text{ for every }}e\in E(G).$$

The restriction $k\geq 4$ is necessary. The 3-vertex-critical graphs are precisely the odd cycles, and every edge of an odd cycle is critical.

History

The study of critical graphs goes back to work of Gabriel Andrew Dirac in the early 1950s. The conjecture separating vertex-criticality from edge-criticality is attributed to Dirac in 1970.

The first example of a vertex-critical graph with no critical edges was constructed by J. I. Brown in 1992; it settled the case $k=5$. In 2002, J. J. Lattanzio proved the conjecture whenever $k-1$ is composite, while Tommy R. Jensen independently proved it for every $k\geq 5$. These results left $k=4$ as the only unresolved case.

In 2012, Jensen and Mark Siggers obtained a partial result for $k=4$. They constructed arbitrarily large 4-vertex-critical graphs having quadratically many non-critical edges but only linearly many critical edges. Consequently, the proportion of edges that are critical can be made arbitrarily small, although their construction does not eliminate all critical edges.

Strengthened form

Paul Erdős proposed a stronger version in the 1980s. For integers $k\geq 4$ and $r\geq 1$, call a graph a $(k,r)$-graph if it is $k$-vertex-critical and deleting any set of at most $r$ edges leaves its chromatic number equal to $k$. Dirac's conjecture is the case $r=1$.

For each $n$, let $f_{k}(n)$ be the largest $r$ for which a $(k,r)$-graph on $n$ vertices exists, taking $f_{k}(n)=0$ if none exists. Erdős asked whether

$$f_{k}(n)\longrightarrow \infty \quad {\text{as }}n\longrightarrow \infty .$$

Ema Skottova and Raphael Steiner proved this for every fixed $k\geq 5$, with the quantitative lower bound $f_{k}(n)=\Omega (n^{1/3})$. They also proved, for every $k\geq 4$, an upper bound of the form

$$f_{k}(n)=O\!\left({\frac {n}{(\log n)^{c}}}\right)$$

for an absolute constant $c>0$. Thus the strengthened problem, like Dirac's original conjecture, remains open only for $k=4$.

Known restrictions in the $k=4$ case

Any $(4,r)$-graph must have edge-connectivity, and hence minimum degree, at least $3r+3$. Its maximum degree is at most $|V(G)|-(2r+3)$, and it has at least $5r+6$ vertices. For Dirac's original case $r=1$, these bounds imply that a putative example has minimum degree at least 6 and at least 11 vertices. One narrower open question is whether a 6-regular $(4,1)$-graph exists.

In September 2026, economist Alex Chan of Harvard Business School posted a working paper proposing a 60-vertex, 6-regular Cayley graph as the missing $k=4$ construction and claiming that it completes Dirac's conjecture; as of that date, the claim had not been peer reviewed.

See also

• Critical graph
• Graph coloring
• Hajós construction

References

Category:Graph coloring Category:Conjectures Category:Unsolved problems in mathematics