Erdős regular graphs of even degree

Andrey A. Dobrynin; Leonid S. Mel'nikov; Artem V. Pyatkin

Discussiones Mathematicae Graph Theory (2007)

  • Volume: 27, Issue: 2, page 269-279
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Andrey A. Dobrynin, Leonid S. Mel'nikov, and Artem V. Pyatkin. "Erdős regular graphs of even degree." Discussiones Mathematicae Graph Theory 27.2 (2007): 269-279. <http://eudml.org/doc/270183>.

@article{AndreyA2007,
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.},
author = {Andrey A. Dobrynin, Leonid S. Mel'nikov, Artem V. Pyatkin},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {vertex coloring; 4-critical graph; circulant; regular graph; vertex connectivity; vertex colouring},
language = {eng},
number = {2},
pages = {269-279},
title = {Erdős regular graphs of even degree},
url = {http://eudml.org/doc/270183},
volume = {27},
year = {2007},
}

TY - JOUR
AU - Andrey A. Dobrynin
AU - Leonid S. Mel'nikov
AU - Artem V. Pyatkin
TI - Erdős regular graphs of even degree
JO - Discussiones Mathematicae Graph Theory
PY - 2007
VL - 27
IS - 2
SP - 269
EP - 279
AB - 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.
LA - eng
KW - vertex coloring; 4-critical graph; circulant; regular graph; vertex connectivity; vertex colouring
UR - http://eudml.org/doc/270183
ER -

References

top
  1. [1] R.L. Brooks, On coloring the nodes of a network, Proc. Cambridge Phil. Soc. 37 (1941) 194-197, doi: 10.1017/S030500410002168X. Zbl0027.26403
  2. [2] Chao Chong-Yun, A critically chromatic graph, Discrete Math. 172 (1997) 3-7, doi: 10.1016/S0012-365X(96)00262-2. 
  3. [3] G.A. Dirac, 4-chrome Graphen Trennende und vollständige 4-Graphen, Math. Nachr. 22 (1960) 51-60, doi: 10.1002/mana.19600220106. Zbl0096.17902
  4. [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. Zbl0096.17903
  5. [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. [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. Zbl1008.05063
  7. [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. Zbl1044.05040
  8. [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. [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. [10] T. Gallai, Kritische Graphen I., Publ. Math. Inst. Hungar. Acad. Sci. 8 (1963) 165-192. 
  11. [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. [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. Zbl0942.05048
  13. [13] T.R. Jensen, Dense critical and vertex-critical graphs, Discrete Math. 258 (2002) 63-84, doi: 10.1016/S0012-365X(02)00262-5. Zbl1007.05048
  14. [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. Zbl0821.05023
  15. [15] T.R. Jensen and B. Toft, Graph Coloring Problems (John Wiley & Sons, USA, 1995). 
  16. [16] G. Koester, Note to a problem of T. Gallai and G.A. Dirac, Combinatorica 5 (1985) 227-228, doi: 10.1007/BF02579365. Zbl0593.05030
  17. [17] G. Koester, 4-critical 4-valent planar graphs constructed with crowns, Math. Scand. 67 (1990) 15-22. Zbl0723.05056
  18. [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. Zbl0756.05070
  19. [19] W. Mader, Über den Zusammenhang symmetrischer Graphen, Arch. Math. (Basel) 21 (1970) 331-336, doi: 10.1007/BF01220924. Zbl0201.56804
  20. [20] W. Mader, Eine Eigenschaft der Atome endlicher Graphen, Arch. Math. (Basel) 22 (1971) 333-336, doi: 10.1007/BF01222585. Zbl0214.51503
  21. [21] A.V. Pyatkin, 6-regular 4-critical graph, J. Graph Theory 41 (2002) 286-291, doi: 10.1002/jgt.10066. Zbl1012.05072
  22. [22] M.E. Watkins, Some classes of hypoconnected vertex-transitive graphs, in: Recent Progress in Combinatorics (Academic Press, New-York, 1969) 323-328. 
  23. [23] M.E. Watkins, Connectivity of transitive graphs, J. Combin. Theory 8 (1970) 23-29, doi: 10.1016/S0021-9800(70)80005-9. Zbl0185.51702
  24. [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. Zbl0766.05031

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.