Regular 4‐critical graphs of even degree
Andrey A. Dobrynin, Leonid S. Mel’nikov, A. V. Pyatkin · Journal of Graph Theory · 2004
Abstract In 1960, Dirac posed the conjecture that r‐connected 4‐critical graphs exist for every r ≥ 3. In 1989, Erdős conjectured that for every r ≥ 3 there exist r‐regular 4‐critical graphs. In this paper, a technique of constructing r‐regular r‐connected vertex‐transitive 4‐critical graphs for even r ≥ 4 is presented. Such graphs are found for r = 6, 8, 10. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 103–130, 2004