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.

Key words： 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