DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

Z. Liang

Zuosong Liang

Qufu Normal University

email: liangzuosong@126.com

Title:

Total coloring of claw-free planar graphs

PDF

Source:

Discussiones Mathematicae Graph Theory 42(3) (2022) 771-777

Received: 2019-05-14 , Revised: 2020-01-19 , Accepted: 2020-01-19 , Available online: 2020-02-04 , https://doi.org/10.7151/dmgt.2300

Abstract:

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 $\Delta(G)$ be the maximum degree of $G$. Vizing conjectured that every graph has a total $(\Delta+2)$-coloring. This Total Coloring Conjecture remains open even for planar graphs, for which the only open case is $\Delta=6$. Claw-free planar graphs have $\Delta\leq 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

References:

  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, 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
Close