×

zbMATH — the first resource for mathematics

On total colorings of 1-planar graphs. (English) Zbl 1317.05066
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, we confirm the total-coloring conjecture for 1-planar graphs with maximum degree at least 13.

MSC:
05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C62 Graph representations (geometric and intersection representations, etc.)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Albertson, MO; Mohar, B, Coloring vertices and faces of locally planar graphs, Graphs Combin, 22, 289-295, (2006) · Zbl 1106.05038
[2] Behzad M (1965) Graphs and their chromatic numbers. Michigan State University, Doctoral thesis · Zbl 1106.05038
[3] Bondy JA, Murty USR (1976) Graph theory with applications. North-Holland, New York · Zbl 1226.05083
[4] Borodin, OV, Solution of ringel’s problems on the vertex-face coloring of plane graphs and on the coloring of \(1\)-planar graphs, Diskret Analiz, 41, 12-26, (1984) · Zbl 0565.05027
[5] Borodin, OV, On the total coloring of planar graphs, J Reine Angew Math, 394, 180-185, (1989) · Zbl 0653.05029
[6] Borodin, OV, A new proof of the \(6\)-color theorem, J Graph Theory, 19, 507-521, (1995) · Zbl 0826.05027
[7] Borodin, OV; Kostochka, AV; Raspaud, A; Sopena, E, Acyclic colouring of 1-planar graphs, Discret Appl Math, 114, 29-41, (2001) · Zbl 0996.05053
[8] Kostochka, AV, The total coloring of a multigraph with maximal degree 4, Discret Math, 17, 161-163, (1977) · Zbl 0411.05038
[9] Kostochka, AV, The total chromatic number of any multigraph with maximum degree five is at most seven, Discret Math, 162, 199-214, (1996) · Zbl 0871.05023
[10] Ringel, G, Ein sechsfarbenproblem auf der kugel, Abh Math Sem Univ Hamburg, 29, 107-117, (1965) · Zbl 0132.20701
[11] Rosenfeld, M, On the total coloring of certain graphs, Israel J Math, 9, 396-402, (1971) · Zbl 0211.56604
[12] Sanders, DP; Zhao, Y, On total 9-coloring planar graphs of maximum degree seven, J Graph Theory, 31, 67-73, (1999) · Zbl 0922.05025
[13] Vijayaditya, N, On total chromatic number of a graph, J Lond Math Soc, 3, 405-408, (1971) · Zbl 0223.05103
[14] Vizing, V, Some unsolved problems in graph theory, Uspekhi Mat Nauk, 23, 117-134, (1968) · Zbl 0177.52301
[15] Wang, W; Lih, K-W, Coupled choosability of plane graphs, J Graph Theory, 58, 27-44, (2008) · Zbl 1155.05016
[16] Yap, HP, Total colorings of graphs, Bull Lond Math Soc, 21, 159-163, (1989) · Zbl 0636.05025
[17] Zhang, X; Liu, G, On edge colorings of 1-planar graphs without chordal 5-cycles, Ars Combin, 104, 431-436, (2012) · Zbl 1274.05186
[18] Zhang, X; Liu, G, On edge colorings of 1-planar graphs without adjacent triangles, Inf Process Lett, 112, 138-142, (2012) · Zbl 1239.05078
[19] Zhang, X; Liu, G; Wu, J-L, Edge coloring of triangle-free 1-planar graphs (in Chinese), J Shandong Univ (Nat Sci), 45, 15-17, (2010) · Zbl 1240.05125
[20] Zhang, X; Liu, G; Wu, J-L, On the linear arboricity of 1-planar graphs, OR Trans, 15, 38-44, (2011) · Zbl 1249.05085
[21] Zhang, X; Liu, G; Wu, J-L, \((1,λ )\)-embedded graphs and acyclic edge choosability, Bull Korean Math Soc, 49, 573-580, (2012) · Zbl 1242.05186
[22] Zhang, X; Wu, J-L, On edge colorings of 1-planar graphs, Inf Process Lett, 111, 124-128, (2011) · Zbl 1259.05050
[23] Zhang, X; Wu, J-L; Liu, G, List edge and List total coloring of 1-planar graphs, Front Math China, 7, 1005-1018, (2012) · Zbl 1254.05050
[24] Zhang, X; Yu, Y; Liu, G, On \((p,1)\)-total labelling of 1-planar graphs, Cent Eur J Math, 9, 1424-1434, (2011) · Zbl 1227.05135
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.