List edge and list total coloring of 1-planar graphs

Abstract

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that each 1-planar graph with maximum degree Δ is (Δ+1)-edge-choosable and (Δ+2)-total-choosable if Δ ⩾ 16, and is Δ-edge-choosable and (Δ+1)-total-choosable if Δ ⩾ 21. The second conclusion confirms the list coloring conjecture for the class of 1-planar graphs with large maximum degree.

Keywords

1-planar graph / list coloring conjecture / discharging

References

[1] Albertson M. O., Mohar B. Coloring vertices and faces of locally planar graphs. Graphs Combin, 2006, 22: 289-295

[2] Bondy J. A., Murty U. S. R. Graph Theory with Applications, 1976, New York: North-Holland

[3] Borodin O. V. Solution of Ringel’s problems on the vertex-face coloring of plane graphs and on the coloring of 1-planar graphs. Diskret Analiz, 1984, 41: 12-26

[4] Borodin O. V. An extension of Kotzig theorem and the list edge coloring of planar graphs. Mat Zametki, 1990, 48: 22-48

[5] Borodin O. V. A new proof of the 6 color theorem. J Graph Theory, 1995, 19(4): 507-521

[6] Borodin O. V., Dmitriev I. G., Ivanova A. O. The height of a 4-cycle in triangle-free 1-planar graphs with minimum degree 5. J Appl Ind Math, 2009, 3(1): 28-31

[7] Borodin O. V., Kostochka A. V., Raspaud A., Sopena E. Acyclic colouring of 1-planar graphs. Discrete Appl Math, 2001, 114: 29-41

[8] Borodin O. V., Kostochka A. V., Woodall D. R. List edge and list total colourings of multigraphs. J Combin Theory Ser B, 1997, 71: 184-204

[9] Fabrici I., Madaras T. The structure of 1-planar graphs. Discrete Math, 2007, 307: 854-865

[10] Harris A. J. Problems and Conjectures in Extremal Graph Theory, 1984, Cambridge: Cambridge University

[11] Hou J., Liu G., Wu J. L. Some results on list total colorings of planar graphs. Lecture Notes in Computer Science, 2007, 4489: 320-328

[12] Hudák D., Madaras T. On local structures of 1-planar graphs of minimum degree 5 and girth 4. Discuss Math Graph Theory, 2009, 29: 385-400

[13] Jensen T. R., Toft B. Graph Coloring Problems, 1995, New York: John Wiley & Sons

[14] Juvan M., Mohar B., Škrekovski R. List total colorings of graphs. Combin Probab Comput, 1998, 7: 181-188

[15] Juvan M., Mohar B., Škrekovski R. Graphs of degree 4 are 5-edge-choosable. J Graph Theory, 1999, 32: 250-262

[16] Ringel G. Ein sechsfarbenproblem auf der Kugel. Abh Math Sem Hamburg Univ, 1965, 29: 107-117

[17] Suzuki Y. Optimal 1-planar graphs which triangulate other surfaces. Discrete Math, 2010, 310: 6-11

[18] Wang W., Lih K. W. Choosability, edge choosability and total choosability of outerplanar graphs. Eur J Combin, 2001, 22: 71-78

[19] Wang W., Lih K. W. Coupled choosability of plane graphs. J Graph Theory, 2008, 58: 27-44

[20] Wu J. L., Wang P. List-edge and list-total colorings of graphs embedded on hyperbolic surfaces. Discrete Math, 2008, 308: 6210-6215

[21] Zhang X., Liu G. On edge colorings of 1-planar graphs without adjacent triangles. Inform Process Lett, 2012, 112(4): 138-142

[22] Zhang X, Liu G. On edge colorings of 1-planar graphs without chordal 5-cycles. Ars Combin, 2012, 104 (in press)

[23] Zhang X., Liu G., Wu J. L. Edge coloring of triangle-free 1-planar graphs. J Shandong Univ (Nat Sci), 2010, 45(6): 15-17

[24] Zhang X., Liu G., Wu J. L. Structural properties of 1-planar graphs and an application to acyclic edge coloring. Sci Sin Math, 2010, 40: 1025-1032

[25] Zhang X., Liu G., Wu J. L. On the linear arboricity of 1-planar graphs. OR Trans, 2011, 15(3): 38-44

[26] Zhang X, Liu G, Wu J L. Light subgraphs in the family of 1-planar graphs with high minimum degree. Acta Math Sin (Engl Ser), doi:10.1007/s10114-011-0439-3

[27] Zhang X., Wu J. L. On edge colorings of 1-planar graphs. Inform Process Lett, 2011, 111(3): 124-128

[28] Zhang X., Wu J. L., Liu G. New upper bounds for the heights of some light subgraphs in 1-planar graphs with high minimum degree. Discrete Math Theor Comput Sci, 2011, 13(3): 9-16

[29] Zhang X., Yu Y., Liu G. On (p, 1)-total labelling of 1-planar graphs. Cent Eur J Math, 2011, 9(6): 1424-1434