Abstract
Graph coloring is an important tool in the study of optimization, computer science, network design, e.g., file transferring in a computer network, pattern matching, computation of Hessians matrix and so on. In this paper, we consider one important coloring, vertex coloring of a total graph, which is familiar to us by the name of “total coloring”. Total coloring is a coloring of \(V\cup {E}\) such that no two adjacent or incident elements receive the same color. In other words, total chromatic number of \(G\) is the minimum number of disjoint vertex independent sets covering a total graph of \(G\). Here, let \(G\) be a planar graph with \(\varDelta \ge 8\). We proved that if for every vertex \(v\in V\), there exists two integers \(i_{v},j_{v} \in \{3,4,5,6,7,8\}\) such that \(v\) is not incident with intersecting \(i_v\)-cycles and \(j_v\)-cycles, then the vertex chromatic number of total graph of \(G\) is \(\varDelta +1\), i.e., the total chromatic number of \(G\) is \(\varDelta +1\).
Similar content being viewed by others
References
Snchez-Arroyo, A.: Determing the total colouring number is NP-hard. Discrete Math. 78, 315–319 (1989)
Bojarshinov, V.A.: Edge and total coloring of interal graphs. Discrete Appl. Math. 114, 23–28 (2001)
Borodin, O.V.: On the total coloring of planar graphs. J. Reine Angew. Math. 394, 180–185 (1989)
Borodin, O.V., Kostochka, A., Woodall, D.: List edge and list total colourings of multigraphs. J. Comb. Theory Ser. B 71, 184–204 (1997)
Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. MacMillan, London (1976)
Chang, J., Wang, H.J., Wu, J.L.: Total coloring of planar graphs with maximum degree 8 and without 5-cycles with two chords. Theor. Comput. Sci. 476, 16–23 (2013)
Chew, K.H., Yap, H.P.: Total chromatic number and chromatic index of complete r-partite graphs. J. Graph Theory 16, 629–634 (1992)
Du, D.Z., Shen, L., Wang, Y.Q.: Planar graphs with maximum degree 8 and without adjacent triangles are 9-totally-colorable. Discrete Appl. Math. 157, 2778–2784 (2009)
Hoffman, D.G., Rodger, C.A.: The chromatic index of complete mutipartite graphs. J. Graphs Theory 16, 159–164 (1992)
Hou, J.F., Wu, J.L., Liu, G.Z., Liu, B.: Total coloring of embedded graphs of maximum degree at least ten. Sci. China Math. 51, 2127–2133 (2008)
Juvan, M., Mohar, B., Skrekovski, R.: List total colourings of graphs. Comb. Probab. Comput. 7, 181–188 (1998)
Kardos̈, F., Král’, D., Sereni, J.S.: The last fraction of a fractional conjecture. SIAM J. Discrete Math. 24, 699–707 (2010)
Kilakos, K., Reed, B.A.: Fractionally colouring total graphs. Combinatorica 12, 435–440 (1993)
Kostochka, A.V.: The total chromatic number of any multigraph with maximum degree five is at most seven. Discrete Math. 162, 199–214 (1996)
Kowalik, L., Sereni, J.-S., S̆krekovski, R.: Total-coloring of plane graphs with maximum degree nine. SIAM J. Discrete Math. 22, 1462–1479 (2008)
Liu, B., Hou, J.F., Wu, J.L., Liu, G.Z.: Total colorings and list total colorings of planar graphs without intersecting 4-cycles. Discrete Math. 309, 6035–6043 (2009)
McDiarmid, C.J.H., Snchez-Arroyo, A.: Total colorings regular bipartite graphs is NP-hard. Discrete Math. 124, 155–162 (1994)
Roussel, N., Zhu, X.: Total coloring of planar graphs of maximum degree eight. Inf. Process. Lett. 110, 321–324 (2010)
Sanders, D.P., Zhao, Y.: On total 9-coloring planar graphs of maximum degree seven. J. Graph Theory 31, 67–73 (1999)
Shen, L., Wang, Y.Q.: Total colorings of planar graphs with maximum degree at least 8. Sci. China Ser. A 52, 1733–1742 (2009)
Shen, L., Wang, Y.Q.: On the 9-total-colorability of planar graphs with maximum degree 8 and without intersecting triangles. Appl. Math. Lett. 22, 1369–1373 (2009)
Wang, G.H., Yan, G.Y., Yu, J.G., Zhang, X.: The \(r\)-acyclic chromatic number of planar graphs. J. Comb. Optim. (2013). doi: 10.1007/s10878-013-9680-2
Wang, H.J., Wu, J.L.: A note on the total coloring of planar graphs without adjacent 4-cycles. Discrete Math. 312, 1923–1926 (2012)
Wang, H.J., Wu, L.D., Wu, W.L., Wu, J.L.: Minimum number of disjoint linear forests covering a planar graph. J. Comb. Optim. (2013). doi:10.1007/s10878-013-9619-7
Wang, W., Lih, K.: Choosability, edge-choosability and total choosability of outerplane graphs. Eur. J. Comb. 22, 71–78 (2001)
Wu, J.L.: Total coloring of series-parallel graphs. Ars Comb. 73, 215–217 (2004)
Wu, J.L., Wang, P.: List-edge and list-total colorings of graphs embedded on hyperbolic surfaces. Discrete Math. 308, 6210–6215 (2008)
Yap, H.P.: Total colourings of graphs. Lecture Notes in Mathematics, vol. 1623. Springer (1996)
Zhang, Z.F., Wang, J.F., Li, H.X.: The total chromatic number of Halin graphs with lower degree (manuscript)
Acknowledgments
This work was supported in part by the National Natural Science Foundation of China under Grants 11201440, 11271006, 11301410, the Natural Science Basic Research Plan in Shaanxi Province of China under Grant 2013JQ1002, and the Scientific Research Foundation for the Excellent Young and Middle-Aged Scientists of Shandong Province of China under Grant BS2013DX002. This work was also supported in part by the National Science Foundation of USA under Grants CNS-0831579 and CCF-0728851.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wang, H., Wu, L., Wu, W. et al. Minimum total coloring of planar graph. J Glob Optim 60, 777–791 (2014). https://doi.org/10.1007/s10898-013-0138-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-013-0138-y