×

Regular 4-critical graphs of even degree. (English) Zbl 1044.05040

A simple graph is \(r\)-critical if its chromatic number equals \(r\) but the deletion of any edge yields a graph with chromatic number \(r-1\). An Erdős graph is an \(r\)-valent 4-critical graph, so called because P. Erdős conjectured in 1989 that such graphs exist for all \(r\geq3\), noting that at that time none was known for \(r\geq6\). A Dirac graph is an \(r\)-connected 4-critical graph, in the light of an analogous conjecture in 1960 by G. A. Dirac.
The main result is a construction of vertex-transitive graphs that are both Erdős and Dirac graphs: one example for \(r=4\), two for \(r=6\), 13 for \(r=8\), and 12 for \(r=10\), the largest having 9817 vertices. As all of the Erdős graphs found here are circulants, the authors inquire whether any others exist and conjecture that their list of 6-valent circulant Erdős graphs is complete.

MSC:

05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
05C40 Connectivity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Boesch, J Graph Theory 8 pp 487– (1984)
[2] Brooks, Proc Cambridge Phil Soc 37 pp 194– (1941)
[3] Chong-Yun, Discrete Math 172 pp 3– (1997)
[4] Dirac, Math Nachr 22 pp 51– (1960)
[5] Dirac, Math Nachr 22 pp 61– (1960)
[6] and 4-chromatic edge-critical regular graphs with high connectivity, Proc Russian Conf Discrete Analysis and Operation Research (DAOR-2002), Novosibirsk, pp. 25-30 (in Russian).
[7] and On 4-chromatic edge-critical regular graphs of high connectivity, Discrete Math 260 (2003) 315-319. · Zbl 1008.05063
[8] On some aspects of my work with Gabriel Dirac, Graph Theory in Memory of G. A. Dirac, Annals of Discrete Mathematics, Vol. 41, and (Editors), North-Holland (now Elsevier). 1989, pp. 111-116.
[9] and Problems and Exercises on Graph Theory and Combinatorics, Novosibirsk State University, Novosibirsk, 1981, (in Russian).
[10] Gallai, Publ Math Inst Hungar Acad Sci 8 pp 165– (1963)
[11] G?bel, Discrete Appl Math 99 pp 3– (2000)
[12] Heuberger, Discrete Math 268 pp 153– (2003)
[13] Structure of critical graphs, Ph.D. Thesis, Odense University, 1996.
[14] Jensen, Discrete Math 258 pp 63– (2002)
[15] Jensen, J Graph Theory 19 pp 107– (1995)
[16] and Graph Coloring Problems, John Wiley & Sons, New York. 1995.
[17] Koester, Combinatorica 5 pp 227– (1985)
[18] Koester, Math Scand 67 pp 15– (1990)
[19] Algebraic combinatorics on words, Cambridge University Press, Cambridge, UK. 2001.
[20] Mader, Arch Math (Basel) 21 pp 331– (1970) · Zbl 0201.56804 · doi:10.1007/BF01220924
[21] Mader, Arch Math (Basel) 22 pp 333– (1971) · doi:10.1007/BF01222585
[22] Pyatkin, J Graph Theory 41 pp 286– (2002)
[23] Some classes of hypoconnected vertex-transitive graphs, Recent Progress in Combinatorics, Academic Press, New York, 1969, pp. 323-328.
[24] Watkins, J Combin Theory 8 pp 23– (1970)
[25] Youngs, Discrete Math 101 pp 343– (1992)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.