# 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

## Access Full Article

top## Abstract

top## How to cite

topAndrey 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] 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] 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. Zbl0096.17902
- [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] 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. Zbl1008.05063
- [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] 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. Zbl0942.05048
- [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] 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] 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. Zbl0593.05030
- [17] G. Koester, 4-critical 4-valent planar graphs constructed with crowns, Math. Scand. 67 (1990) 15-22. Zbl0723.05056
- [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] W. Mader, Über den Zusammenhang symmetrischer Graphen, Arch. Math. (Basel) 21 (1970) 331-336, doi: 10.1007/BF01220924. Zbl0201.56804
- [20] W. Mader, Eine Eigenschaft der Atome endlicher Graphen, Arch. Math. (Basel) 22 (1971) 333-336, doi: 10.1007/BF01222585. Zbl0214.51503
- [21] A.V. Pyatkin, 6-regular 4-critical graph, J. Graph Theory 41 (2002) 286-291, doi: 10.1002/jgt.10066. Zbl1012.05072
- [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. Zbl0185.51702
- [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 ?

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