# The structure of plane graphs with independent crossings and its applications to coloring problems

Open Mathematics (2013)

- Volume: 11, Issue: 2, page 308-321
- ISSN: 2391-5455

## Access Full Article

top## Abstract

top## How to cite

topXin Zhang, and Guizhen Liu. "The structure of plane graphs with independent crossings and its applications to coloring problems." Open Mathematics 11.2 (2013): 308-321. <http://eudml.org/doc/269573>.

@article{XinZhang2013,

abstract = {If a graph G has a drawing in the plane in such a way that every two crossings are independent, then we call G a plane graph with independent crossings or IC-planar graph for short. In this paper, the structure of IC-planar graphs with minimum degree at least two or three is studied. By applying their structural results, we prove that the edge chromatic number of G is Δ if Δ ≥ 8, the list edge (resp. list total) chromatic number of G is Δ (resp. Δ + 1) if Δ ≥ 14 and the linear arboricity of G is ℈Δ/2⌊ if Δ ≥ 17, where G is an IC-planar graph and Δ is the maximum degree of G.},

author = {Xin Zhang, Guizhen Liu},

journal = {Open Mathematics},

keywords = {Independent crossing; IC-planar graph; Light edge; Coloring; Discharging; independent crossing; independent crossing planar graph; light edge; coloring; discharging},

language = {eng},

number = {2},

pages = {308-321},

title = {The structure of plane graphs with independent crossings and its applications to coloring problems},

url = {http://eudml.org/doc/269573},

volume = {11},

year = {2013},

}

TY - JOUR

AU - Xin Zhang

AU - Guizhen Liu

TI - The structure of plane graphs with independent crossings and its applications to coloring problems

JO - Open Mathematics

PY - 2013

VL - 11

IS - 2

SP - 308

EP - 321

AB - If a graph G has a drawing in the plane in such a way that every two crossings are independent, then we call G a plane graph with independent crossings or IC-planar graph for short. In this paper, the structure of IC-planar graphs with minimum degree at least two or three is studied. By applying their structural results, we prove that the edge chromatic number of G is Δ if Δ ≥ 8, the list edge (resp. list total) chromatic number of G is Δ (resp. Δ + 1) if Δ ≥ 14 and the linear arboricity of G is ℈Δ/2⌊ if Δ ≥ 17, where G is an IC-planar graph and Δ is the maximum degree of G.

LA - eng

KW - Independent crossing; IC-planar graph; Light edge; Coloring; Discharging; independent crossing; independent crossing planar graph; light edge; coloring; discharging

UR - http://eudml.org/doc/269573

ER -

## References

top- [1] Akiyama J., Exoo G., Harary F., Covering and packing in graphs. III: Cyclic and acyclic invariants, Math. Slovaca, 1980, 30(4), 405–417 Zbl0458.05050
- [2] Albertson M.O., Chromatic number, independence ratio, and crossing number, Ars Math. Contemp., 2008, 1(1), 1–6 Zbl1181.05032
- [3] Bondy J.A., Murty U.S.R., Graph Theory with Applications, Elsevier, New York, 1976 Zbl1226.05083
- [4] Borodin O.V., Solution of the Ringel problem on the vertex-face coloring of plane graphs and on the coloring of 1-planar graphs, Metody Diskret. Analiz., 1984, 41, 12–26
- [5] Borodin O.V., A new proof of the 6-color theorem, J. Graph Theory, 1995, 19(4), 507–521 http://dx.doi.org/10.1002/jgt.3190190406 Zbl0826.05027
- [6] Borodin O.V., Kostochka A.V., Woodall D.R., List edge and list total colorings of multigraphs, J. Combin. Theory Ser. B, 1997, 71(2), 184–204 http://dx.doi.org/10.1006/jctb.1997.1780 Zbl0876.05032
- [7] Cygan M., Hou J.-F., Kowalik Ł., Lužar B., Wu J.-L., A planar linear arboricity conjecture, J. Graph Theory, 2012, 69(4), 403–425 http://dx.doi.org/10.1002/jgt.20592 Zbl1242.05064
- [8] Erman R., Havet F., Lidický B., Pangrác O., 5-coloring graphs with 4 crossings, SIAM J. Discrete Math., 2011, 25(1), 401–422 http://dx.doi.org/10.1137/100784059 Zbl1232.05078
- [9] Fabrici I., Madaras T., The structure of 1-planar graphs, Discrete Math., 2007, 307(7–8), 854–865 http://dx.doi.org/10.1016/j.disc.2005.11.056 Zbl1111.05026
- [10] Jensen T.R., Toft B., Graph Coloring Problems, Wiley-Intersci. Ser. Discrete Math. Optim., John Wiley & Sons, New York, 1995 Zbl0855.05054
- [11] Král D., Stacho L., Coloring plane graphs with independent crossings, J. Graph Theory, 2010, 64(3), 184–205 Zbl1208.05019
- [12] Li X., Average degrees of critical graphs, Ars Combin., 2005, 74, 303–322 Zbl1074.05037
- [13] Pach J., Tóth G., Graphs drawn with few crossings per edge, Combinatorica, 1997, 17(3), 427–439 http://dx.doi.org/10.1007/BF01215922 Zbl0902.05017
- [14] Ringel G., Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Sem. Univ. Hamburg, 1965, 29, 107–117 http://dx.doi.org/10.1007/BF02996313 Zbl0132.20701
- [15] Sanders D.P., Zhao Y., On total 9-coloring planar graphs of maximum degree seven, J. Graph Theory, 1999, 31(1), 67–73 http://dx.doi.org/10.1002/(SICI)1097-0118(199905)31:1<67::AID-JGT6>3.0.CO;2-C
- [16] Sanders D.P., Zhao Y., Planar graphs of maximum degree seven are class I, J. Combin. Theory Ser. B, 2001, 83(2), 201–212 http://dx.doi.org/10.1006/jctb.2001.2047 Zbl1024.05031
- [17] Vizing V.G., Critical graphs with given chromatic class, Diskret. Analiz., 1965, 5, 9–17
- [18] Wu J.-L., On the linear arboricity of planar graphs, J. Graph Theory, 1999, 31(2), 129–134 http://dx.doi.org/10.1002/(SICI)1097-0118(199906)31:2<129::AID-JGT5>3.0.CO;2-A
- [19] Wu J., Wang P., List-edge and list-total colorings of graphs embedded on hyperbolic surfaces, Discrete Math., 2008, 308(4), 6210–6215 http://dx.doi.org/10.1016/j.disc.2007.11.044 Zbl1189.05067
- [20] Wu J.-L., Wu Y.-W., The linear arboricity of planar graphs of maximum degree seven is four, J. Graph Theory, 2008, 58(3), 210–220 http://dx.doi.org/10.1002/jgt.20305 Zbl1158.05023
- [21] Zhang X., Hou J., Liu G., On total colorings of 1-planar graphs, preprint available at http://xinzhang.hpage.com/get_file.php?id=1513981&vnr=342077 Zbl1317.05066
- [22] Zhang X., Wu J.-L., On edge colorings of 1-planar graphs, Inform. Process. Lett., 2011, 111(3), 124–128 http://dx.doi.org/10.1016/j.ipl.2010.11.001 Zbl1259.05050
- [23] Zhang X., Wu J., Liu G., List edge and list total coloring of 1-planar graphs, Front. Math. China (in press), DOI: 10.1007/s11464-012-0184-7 Zbl1254.05050

## NotesEmbed ?

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