Download PDF - Erdős regular graphs of even degreeAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Erdős regular graphs of even degree

Authors 1, 1, 1

Affiliations

  1. Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, Novosibirsk 630090, Russia

Abstract

In 1960, Dirac put forward 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. A method for finding r-regular 4-critical graphs and the numbers of such graphs for r ≤ 10 have been reported in [6,7]. Results of a computer search for graphs of degree r = 12,14,16 are presented. All the graphs found are both r-regular and r-connected.

Keywords

ENG
vertex coloring, 4-critical graph, circulant, regular graph, vertex connectivity

Bibliography

  1. R.L. Brooks, On coloring the nodes of a network, Proc. Cambridge Phil. Soc. 37 (1941) 194-197, doi: 10.1017/S030500410002168X.
  2. Chao Chong-Yun, A critically chromatic graph, Discrete Math. 172 (1997) 3-7, doi: 10.1016/S0012-365X(96)00262-2.
  3. G.A. Dirac, 4-chrome Graphen Trennende und vollständige 4-Graphen, Math. Nachr. 22 (1960) 51-60, doi: 10.1002/mana.19600220106.
  4. G.A. Dirac, In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen, Math. Nachr. 22 (1960) 61-85, doi: 10.1002/mana.19600220107.
  5. A.A. Dobrynin, L.S. Mel'nikov and A.V. Pyatkin, 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).
  6. A.A. Dobrynin, L.S. Mel'nikov and A.V. Pyatkin, On 4-chromatic edge-critical regular graphs of high connectivity, Discrete Math. 260 (2003) 315-319, doi: 10.1016/S0012-365X(02)00668-4.
  7. A.A. Dobrynin, L.S. Mel'nikov and A.V. Pyatkin, Regular 4-critical graphs of even degree, J. Graph Theory 46 (2004) 103-130, doi: 10.1002/jgt.10176.
  8. P. Erdös, On some aspects of my work with Gabriel Dirac, in: L.D. Andersen, I.T. Jakobsen, C. Thomassen, B. Toft and P.D. Vestergaard (Eds.), Graph Theory in Memory of G.A. Dirac, Annals of Discrete Mathematics, Vol. 41, North-Holland, 1989, pp. 111-116.
  9. V.A. Evstigneev and L.S. Mel'nikov, Problems and Exercises on Graph Theory and Combinatorics (Novosibirsk State University, Novosibirsk, 1981) (in Russian).
  10. T. Gallai, Kritische Graphen I., Publ. Math. Inst. Hungar. Acad. Sci. 8 (1963) 165-192.
  11. M.R. Garey and D.S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness (W.H. Freeman and Company, San Francisco, 1979).
  12. F. Göbel and E.A. Neutel, Cyclic graphs, Discrete Appl. Math. 99 (2000) 3-12, doi: 10.1016/S0166-218X(99)00121-3.
  13. T.R. Jensen, Dense critical and vertex-critical graphs, Discrete Math. 258 (2002) 63-84, doi: 10.1016/S0012-365X(02)00262-5.
  14. T.R. Jensen and G.F. Royle, Small graphs of chromatic number 5: a computer search, J. Graph Theory 19 (1995) 107-116, doi: 10.1002/jgt.3190190111.
  15. T.R. Jensen and B. Toft, Graph Coloring Problems (John Wiley & Sons, USA, 1995).
  16. G. Koester, Note to a problem of T. Gallai and G.A. Dirac, Combinatorica 5 (1985) 227-228, doi: 10.1007/BF02579365.
  17. G. Koester, 4-critical 4-valent planar graphs constructed with crowns, Math. Scand. 67 (1990) 15-22.
  18. G. Koester, On 4-critical planar graphs with high edge density, Discrete Math. 98 (1991) 147-151, doi: 10.1016/0012-365X(91)90039-5.
  19. W. Mader, Über den Zusammenhang symmetrischer Graphen, Arch. Math. (Basel) 21 (1970) 331-336, doi: 10.1007/BF01220924.
  20. W. Mader, Eine Eigenschaft der Atome endlicher Graphen, Arch. Math. (Basel) 22 (1971) 333-336, doi: 10.1007/BF01222585.
  21. A.V. Pyatkin, 6-regular 4-critical graph, J. Graph Theory 41 (2002) 286-291, doi: 10.1002/jgt.10066.
  22. M.E. Watkins, Some classes of hypoconnected vertex-transitive graphs, in: Recent Progress in Combinatorics (Academic Press, New-York, 1969) 323-328.
  23. M.E. Watkins, Connectivity of transitive graphs, J. Combin. Theory 8 (1970) 23-29, doi: 10.1016/S0021-9800(70)80005-9.
  24. D.A. Youngs, Gallai's problem on Dirac's construction, Discrete Math. 101 (1992) 343-350, doi: 10.1016/0012-365X(92)90615-M.
Discussiones Mathematicae Graph Theory
2007/27/2
Export to PBN, Opens in new tab
Pages:
269-279
Main language of publication
English
Received
2006-02-09
Accepted
2007-02-28
Published
2007

DOI: 10.7151/dmgt.1360

Exact and natural sciences