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

Xin Zhang; Guizhen Liu

Open Mathematics (2013)

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

Abstract

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

How to cite

top

Xin 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. [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. [2] Albertson M.O., Chromatic number, independence ratio, and crossing number, Ars Math. Contemp., 2008, 1(1), 1–6 Zbl1181.05032
  3. [3] Bondy J.A., Murty U.S.R., Graph Theory with Applications, Elsevier, New York, 1976 Zbl1226.05083
  4. [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. [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. [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. [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. [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. [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. [10] Jensen T.R., Toft B., Graph Coloring Problems, Wiley-Intersci. Ser. Discrete Math. Optim., John Wiley & Sons, New York, 1995 Zbl0855.05054
  11. [11] Král D., Stacho L., Coloring plane graphs with independent crossings, J. Graph Theory, 2010, 64(3), 184–205 Zbl1208.05019
  12. [12] Li X., Average degrees of critical graphs, Ars Combin., 2005, 74, 303–322 Zbl1074.05037
  13. [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. [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. [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. [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. [17] Vizing V.G., Critical graphs with given chromatic class, Diskret. Analiz., 1965, 5, 9–17 
  18. [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. [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. [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. [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. [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. [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 ?

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.