|
|
|
List edge and list total coloring of 1-planar graphs |
Xin ZHANG, Jianliang WU, Guizhen LIU( ) |
| School of Mathematics, Shandong University, Jinan 250100, China |
|
|
|
|
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
|
|
Corresponding Author(s):
LIU Guizhen,Email:gzliu@sdu.edu.cn
|
|
Issue Date: 01 October 2012
|
|
| 1 |
Albertson M O, Mohar B. Coloring vertices and faces of locally planar graphs. Graphs Combin , 2006, 22: 289-295
doi: 10.1007/s00373-006-0653-4
|
| 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
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
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
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
doi: 10.1006/jctb.1997.1780
|
| 9 |
Fabrici I, Madaras T. The structure of 1-planar graphs. Discrete Math , 2007, 307: 854-865
doi: 10.1016/j.disc.2005.11.056
|
| 10 |
Harris A J. Problems and Conjectures in Extremal Graph Theory. . 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
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
doi: 10.7151/dmgt.1454
|
| 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
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
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
doi: 10.1007/BF02996313
|
| 17 |
Suzuki Y. Optimal 1-planar graphs which triangulate other surfaces. Discrete Math , 2010, 310: 6-11
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
doi: 10.1006/eujc.2000.0430
|
| 19 |
Wang W, Lih K W. Coupled choosability of plane graphs. J Graph Theory , 2008, 58: 27-44
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
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
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)
|
| 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) ,
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
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
