×

List edge and list total coloring of 1-planar graphs. (English) Zbl 1254.05050

Summary: 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 \(\Delta\) is (\(\Delta+1\))-edge-choosable and (\(\Delta+2\))-total-choosable if \(\Delta \geqslant 16\), and is \(\Delta\)-edge-choosable and (\(\Delta+1\))-total-choosable if \(\Delta \geqslant 21\). The second conclusion confirms the list coloring conjecture for the class of 1-planar graphs with large maximum degree.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
05C07 Vertex degrees
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albertson M O, Mohar B. Coloring vertices and faces of locally planar graphs. Graphs Combin, 2006, 22: 289–295 · Zbl 1106.05038 · doi:10.1007/s00373-006-0653-4
[2] Bondy J A, Murty U S R. Graph Theory with Applications. New York: North-Holland, 1976 · Zbl 1226.05083
[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) · Zbl 0565.05027
[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 · Zbl 0826.05027 · doi:10.1002/jgt.3190190406
[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 · Zbl 1249.05203 · doi:10.1134/S1990478909010049
[7] Borodin O V, Kostochka A V, Raspaud A, Sopena E. Acyclic colouring of 1-planar graphs. Discrete Appl Math, 2001, 114: 29–41 · Zbl 0996.05053 · doi:10.1016/S0166-218X(00)00359-0
[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 · Zbl 0876.05032 · doi:10.1006/jctb.1997.1780
[9] Fabrici I, Madaras T. The structure of 1-planar graphs. Discrete Math, 2007, 307: 854–865 · Zbl 1111.05026 · doi:10.1016/j.disc.2005.11.056
[10] Harris A J. Problems and Conjectures in Extremal Graph Theory. Ph D Dissertation. 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 · Zbl 05293786 · doi:10.1007/978-3-540-72588-6_53
[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 · Zbl 1194.05025 · doi:10.7151/dmgt.1454
[13] Jensen T R, Toft B. Graph Coloring Problems. New York: John Wiley & Sons, 1995 · Zbl 0855.05054
[14] Juvan M, Mohar B, Škrekovski R. List total colorings of graphs. Combin Probab Comput, 1998, 7: 181–188 · Zbl 0911.05033 · doi:10.1017/S0963548397003210
[15] Juvan M, Mohar B, Škrekovski R. Graphs of degree 4 are 5-edge-choosable. J Graph Theory, 1999, 32: 250–262 · Zbl 0934.05052 · doi:10.1002/(SICI)1097-0118(199911)32:3<250::AID-JGT5>3.0.CO;2-R
[16] Ringel G. Ein sechsfarbenproblem auf der Kugel. Abh Math Sem Hamburg Univ, 1965, 29: 107–117 · Zbl 0132.20701 · doi:10.1007/BF02996313
[17] Suzuki Y. Optimal 1-planar graphs which triangulate other surfaces. Discrete Math, 2010, 310: 6–11 · Zbl 1188.05056 · doi:10.1016/j.disc.2009.07.016
[18] Wang W, Lih K W. Choosability, edge choosability and total choosability of outerplanar graphs. Eur J Combin, 2001, 22: 71–78 · Zbl 0972.05021 · doi:10.1006/eujc.2000.0430
[19] Wang W, Lih K W. Coupled choosability of plane graphs. J Graph Theory, 2008, 58: 27–44 · Zbl 1155.05016 · doi:10.1002/jgt.20292
[20] Wu J L, Wang P. List-edge and list-total colorings of graphs embedded on hyperbolic surfaces. Discrete Math, 2008, 308: 6210–6215 · Zbl 1189.05067 · doi:10.1016/j.disc.2007.11.044
[21] Zhang X, Liu G. On edge colorings of 1-planar graphs without adjacent triangles. Inform Process Lett, 2012, 112(4): 138–142 · Zbl 1239.05078 · doi:10.1016/j.ipl.2011.10.021
[22] Zhang X, Liu G. On edge colorings of 1-planar graphs without chordal 5-cycles. Ars Combin, 2012, 104 (in press) · Zbl 1274.05186
[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) · Zbl 1240.05125
[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 · Zbl 1249.05085
[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 · Zbl 1252.05047
[27] Zhang X, Wu J L. On edge colorings of 1-planar graphs. Inform Process Lett, 2011, 111(3): 124–128 · Zbl 1259.05050 · doi:10.1016/j.ipl.2010.11.001
[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 · Zbl 1283.05075
[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 · Zbl 1227.05135 · doi:10.2478/s11533-011-0092-1
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.