Geodesic
Total Coloring of Claw-Free Planar Graphs
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 771-777.

Voir la notice de l'article provenant de la source Library of Science

A total coloring of a graph is an assignment of colors to both its vertices and edges so that adjacent or incident elements acquire distinct colors. Let Δ(G) be the maximum degree of G. Vizing conjectured that every graph has a total (Δ + 2)-coloring. This Total Coloring Conjecture remains open even for planar graphs, for which the only open case is Δ = 6. Claw-free planar graphs have Δ ≤ 6. In this paper, we prove that the Total Coloring Conjecture holds for claw-free planar graphs.
Keywords: total coloring, total coloring conjecture, planar graph, claw 
@article{DMGT_2022_42_3_a5,
     author = {Liang, Zuosong},
     title = {Total {Coloring} of {Claw-Free} {Planar} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {771--777},
     publisher = {mathdoc},
     volume = {42},
     number = {3},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a5/}
}
TY  - JOUR
AU  - Liang, Zuosong
TI  - Total Coloring of Claw-Free Planar Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 771
EP  - 777
VL  - 42
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a5/
LA  - en
ID  - DMGT_2022_42_3_a5
ER  - 
%0 Journal Article
%A Liang, Zuosong
%T Total Coloring of Claw-Free Planar Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 771-777
%V 42
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a5/
%G en
%F DMGT_2022_42_3_a5
Liang, Zuosong. Total Coloring of Claw-Free Planar Graphs. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 771-777. http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a5/

[1] L. Andersen, Total Colouring of Simple Graphs, Master’s Thesis (University of Aalborg, 1993).

[2] M. Behzad, Graphs and Their Chromatic Numbers, PhD Thesis (Michigan State University, 1965).

[3] V.A. Bojarshinov, Edge and total coloring of interval graphs, Discrete Appl. Math. 114 (2001) 23–28. https://doi.org/10.1016/S0166-218X(00)00358-9

[4] O.V. Borodin, On the total coloring of planar graphs, J. Reine Angew. Math. 394 (1989) 180–185. https://doi.org/10.1515/crll.1989.394.180

[5] O.V. Borodin, A.V. Kostochka and D.R. Woodall, List edge and list total colourings of multigraphs, J. Combin. Theory Ser. B 71 (1997) 184–204. https://doi.org/10.1006/jctb.1997.1780

[6] B.-L. Chen, H.-L. Fu and M.T. Ko, Total chromatic number and chromatic index of split graphs, J. Combin. Math. Combin. Comput. 17 (1995) 137–146.

[7] C.M.H. de Figueiredo, J. Meidanis and C.P. de Mello, Total-chromatic number and chromatic index of dually chordal graphs, Inform. Process. Lett. 70 (1999) 147–152. https://doi.org/10.1016/S0020-0190(99)00050-2

[8] Ł. Kowalik, J.S. Sereni and R. Škrekovski, Total-coloring of plane graphs with maximum degree nine, SIAM J. Discrete Math. 22 (2008) 1462–1479. https://doi.org/10.1137/070688389

[9] A.V. Kostochka, The total coloring of a multigraph with maximal degree 4, Discrete Math. 17 (1977) 161–163. https://doi.org/10.1016/0012-365X(77)90146-7

[10] A.V. Kostochka, Exact upper bound for the total chromatic number of a graph, in: Proc. 24th Int. Wiss. Koll. Tech. Hochsch. Ilmenau (1979) 33–36, in Russian.

[11] A.V. Kostochka, The total chromatic number of any multigraph with maximum degree five is at most seven, Discrete Math. 162 (1996) 199–214. https://doi.org/10.1016/0012-365X(95)00286-6

[12] M.D. Plummer, Extending matchings in claw-free graphs, Discrete Math. 125 (1994) 301–307. https://doi.org/10.1016/0012-365X(94)90171-6

[13] M. Rosenfeld, On the total coloring of certain graphs, Israel J. Math. 9 (1971) 396–402. https://doi.org/10.1007/BF02771690

[14] D.P. Sanders and Y. Zhao, On total 9 -coloring planar graphs of maximum degree seven, J. Graph Theory 31 (1999) 67–73. https://doi.org/10.1002/(SICI)1097-0118(199905)31:1¡67::AID-JGT6¿3.0.CO;2-C

[15] E.F. Shan, Z.S. Liang and L.Y. Kang, Clique-transversal sets and clique-coloring in planar graphs, European J. Combin. 36 (2014) 367–376. https://doi.org/10.1016/j.ejc.2013.08.003

[16] N. Vijayaditya, On total chromatic number of a graph, J. London Math. Soc. (2) 3 (1971) 405–408. https://doi.org/10.1112/jlms/s2-3.3.405

[17] V.G. Vizing, Some unsolved problems in graph theory, Uspekhi Mat. Nauk 23 (1968) 117–134, English translation in Russian Math. Surveys 23 (1968) 125–141, in Russian. https://doi.org/10.1070/RM1968v023n06ABEH001252

[18] W.F. Wang, Total chromatic number of planar graphs with maximum degree ten, J. Graph Theory 54 (2007) 91–102. https://doi.org/10.1002/jgt.20195

[19] B. Wang and J.-L. Wu, Total colorings of planar graphs with maximum degree seven and without intersecting 3 -cycles, Discrete Math. 311 (2011) 2025–2030. https://doi.org/10.1016/j.disc.2011.05.038

[20] P. Wang and J.-L. Wu, A note on total colorings of planar graphs without 4 -cycles, Discuss. Math. Graph Theory 24 (2004) 125–135. https://doi.org/10.7151/dmgt.1219

[21] H.-P. Yap, Total Colourings of Graphs, in: Lecture Notes in Math. 1623 (Springer, Berlin, Heidelberg, 1996). https://doi.org/10.1007/BFb0092895