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. New York: North-Holland, 1976

[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 (in Russian)

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

[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. <DissertationTip/>. Cambridge: Cambridge University, 1984

[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. New York: John Wiley & Sons, 1995

[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 (in Chinese)

[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 (in Chinese)

[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),

[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

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg