Geodesic
On local structure of 1-planar graphs of minimum degree 5 and girth 4
Discussiones Mathematicae. Graph Theory, Tome 29 (2009) no. 2, pp. 385-400.

Voir la notice de l'article provenant de la source Library of Science

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
Keywords: light graph, 1-planar graph, star, cycle 
@article{DMGT_2009_29_2_a12,
     author = {Hud\'ak, D\'avid and Madaras, Tom\'as},
     title = {On local structure of 1-planar graphs of minimum degree 5 and girth 4},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {385--400},
     publisher = {mathdoc},
     volume = {29},
     number = {2},
     year = {2009},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2009_29_2_a12/}
}
TY  - JOUR
AU  - Hudák, Dávid
AU  - Madaras, Tomás
TI  - On local structure of 1-planar graphs of minimum degree 5 and girth 4
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2009
SP  - 385
EP  - 400
VL  - 29
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2009_29_2_a12/
LA  - en
ID  - DMGT_2009_29_2_a12
ER  - 
%0 Journal Article
%A Hudák, Dávid
%A Madaras, Tomás
%T On local structure of 1-planar graphs of minimum degree 5 and girth 4
%J Discussiones Mathematicae. Graph Theory
%D 2009
%P 385-400
%V 29
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2009_29_2_a12/
%G en
%F DMGT_2009_29_2_a12
Hudák, Dávid; Madaras, Tomás. On local structure of 1-planar graphs of minimum degree 5 and girth 4. Discussiones Mathematicae. Graph Theory, Tome 29 (2009) no. 2, pp. 385-400. http://geodesic.mathdoc.fr/item/DMGT_2009_29_2_a12/

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

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

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

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

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

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

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

[10] V.P. Korzhik, Minimal non-1-planar graphs, Discrete Math. 308 (2008) 1319-1327, doi: 10.1016/j.disc.2007.04.009.

[11] G. Ringel, Ein Sechsfarbenproblem auf der Kügel, Abh. Math. Sem. Univ. Hamburg 29 (1965) 107-117, doi: 10.1007/BF02996313.

[12] H. Schumacher, Zur Structur 1-planar Graphen, Math. Nachr. 125 (1986) 291-300.