On local structure of 1-planar graphs of minimum degree 5 and girth 4

Dávid Hudák; Tomás Madaras

Discussiones Mathematicae Graph Theory (2009)

  • Volume: 29, Issue: 2, page 385-400
  • ISSN: 2083-5892

Abstract

top
A graph is 1-planar if it can be embedded in the plane so that each edge is crossed by at most one other edge. We prove that each 1-planar graph of minimum degree 5 and girth 4 contains (1) a 5-vertex adjacent to an ≤ 6-vertex, (2) a 4-cycle whose every vertex has degree at most 9, (3) a K 1 , 4 with all vertices having degree at most 11.

How to cite

top

Dávid Hudák, and Tomás Madaras. "On local structure of 1-planar graphs of minimum degree 5 and girth 4." Discussiones Mathematicae Graph Theory 29.2 (2009): 385-400. <http://eudml.org/doc/270802>.

@article{DávidHudák2009,
abstract = {A graph is 1-planar if it can be embedded in the plane so that each edge is crossed by at most one other edge. We prove that each 1-planar graph of minimum degree 5 and girth 4 contains (1) a 5-vertex adjacent to an ≤ 6-vertex, (2) a 4-cycle whose every vertex has degree at most 9, (3) a $K_\{1,4\}$ with all vertices having degree at most 11.},
author = {Dávid Hudák, Tomás Madaras},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {light graph; 1-planar graph; star; cycle},
language = {eng},
number = {2},
pages = {385-400},
title = {On local structure of 1-planar graphs of minimum degree 5 and girth 4},
url = {http://eudml.org/doc/270802},
volume = {29},
year = {2009},
}

TY - JOUR
AU - Dávid Hudák
AU - Tomás Madaras
TI - On local structure of 1-planar graphs of minimum degree 5 and girth 4
JO - Discussiones Mathematicae Graph Theory
PY - 2009
VL - 29
IS - 2
SP - 385
EP - 400
AB - A graph is 1-planar if it can be embedded in the plane so that each edge is crossed by at most one other edge. We prove that each 1-planar graph of minimum degree 5 and girth 4 contains (1) a 5-vertex adjacent to an ≤ 6-vertex, (2) a 4-cycle whose every vertex has degree at most 9, (3) a $K_{1,4}$ with all vertices having degree at most 11.
LA - eng
KW - light graph; 1-planar graph; star; cycle
UR - http://eudml.org/doc/270802
ER -

References

top
  1. [1] O.V. Borodin, Solution of Kotzig-Grünbaum problems on separation of a cycle in planar graphs (Russian), Mat. Zametki 46 (1989) 9-12; translation in Math. Notes 46 (1989) 835-837, doi: 10.1007/BF01139613. Zbl0694.05027
  2. [2] O.V. Borodin, Solution of the Ringel problem on vertex-face coloring of planar graphs and coloring of 1-planar graphs, Metody Diskret. Analiz. 41 (1984) 12-26 (in Russian). 
  3. [3] O.V. Borodin, A new proof of the 6 color theorem, J. Graph Theory 19 (1995) 507-521, doi: 10.1002/jgt.3190190406. Zbl0826.05027
  4. [4] O.V. Borodin, A.V. Kostochka, A. Raspaud and E. Sopena, Acyclic coloring of 1-planar graphs (Russian), Diskretn. Anal. Issled. Oper. 6 (1999) 20-35; translation in Discrete Appl. Math. 114 (2001) 29-41. Zbl0931.05032
  5. [5] Z.-Z. Chen and M. Kouno, A linear-time algorithm for 7-coloring 1-plane graphs, Algorithmica 43 (2005) 147-177, doi: 10.1007/s00453-004-1134-x. Zbl1082.05084
  6. [6] R. Diestel, Graph Theory (Springer, New York, 1997). 
  7. [7] I. Fabrici and T. Madaras, The structure of 1-planar graphs, Discrete Math. 307 (2007) 854-865, doi: 10.1016/j.disc.2005.11.056. Zbl1111.05026
  8. [8] S. Jendrol' and T. Madaras, On light subgraphs in plane graphs of minimum degree five, Discuss. Math. Graph Theory 16 (1996) 207-217, doi: 10.7151/dmgt.1035. Zbl0877.05050
  9. [9] S. Jendrol', T. Madaras, R. Soták and Z. Tuza, On light cycles in plane triangulations, Discrete Math. 197/198 (1999) 453-467, doi: 10.1016/S0012-365X(99)90099-7. Zbl0936.05065
  10. [10] V.P. Korzhik, Minimal non-1-planar graphs, Discrete Math. 308 (2008) 1319-1327, doi: 10.1016/j.disc.2007.04.009. Zbl1132.05014
  11. [11] G. Ringel, Ein Sechsfarbenproblem auf der Kügel, Abh. Math. Sem. Univ. Hamburg 29 (1965) 107-117, doi: 10.1007/BF02996313. Zbl0132.20701
  12. [12] H. Schumacher, Zur Structur 1-planar Graphen, Math. Nachr. 125 (1986) 291-300. Zbl0594.05026

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.