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

Discussiones Mathematicae Graph Theory (2009)

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

## Access Full Article

top## Abstract

top## How to cite

topDá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] 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] 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] 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] 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] 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] R. Diestel, Graph Theory (Springer, New York, 1997).
- [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] 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] 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] 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] G. Ringel, Ein Sechsfarbenproblem auf der Kügel, Abh. Math. Sem. Univ. Hamburg 29 (1965) 107-117, doi: 10.1007/BF02996313. Zbl0132.20701
- [12] H. Schumacher, Zur Structur 1-planar Graphen, Math. Nachr. 125 (1986) 291-300. Zbl0594.05026

## Citations in EuDML Documents

top## NotesEmbed ?

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