Total coloring is a function that assigns colors to the vertices and edges of the graph such that the adjacent and the incident elements receive different colors. The minimum number of colors required for a proper total coloring of a graph $G$ is called the total chromatic number of $G$ and is denoted by $χ^{″} (G)$ . Behzad–Vizing conjecture (Total Coloring Conjecture) states that for any graph $G$ , $χ^{″} (G) \leq Δ (G) + 2$ , where $Δ (G)$ is the maximum degree of $G$ . In this paper, we verify the Behzad–Vizing conjecture for some product graphs.

Communicated by Guanghui Wang

Keywords:

AMSC: 05C15, 05C76

References

1. M. Behzad, Graphs and their chromatic numbers, doctoral thesis, Michigan State University (1965). Google Scholar
2. O. V. Borodin , Colorings of plane graphs: A survey, Discrete Math. 313(4) (1989) 517–539. Crossref, Google Scholar
3. D. Castonguay, C. M. H. de Figueiredo, L. A. B. Kowada, C. S. R. Patrao, D. Sasaki and M. Valencia-Pabon , On total coloring the direct product of complete graphs, Procedia Comput. Sci. 195 (2021) 306–314. Crossref, Google Scholar
4. D. Castonguay, C. M. H. de Figueiredo, L. A. B. Kowada, C. S. R. Patrao and D. Sasaki , On total coloring the direct product of cycles and bipartite direct product of graphs, Discrete Math. 346(6) (2023) 113340. Crossref, Google Scholar
5. J. Geetha and K. Somasundaram , Total colorings of product graphs, Graphs Comb. 34(2) (2018) 339–347. Crossref, Google Scholar
6. J. Geetha, N. Narayanan and K. Somasundaram , Total coloring — A survey, AKCE Int. J. Graphs Combin. (2023) 1–13. Google Scholar
7. A. J. W. Hilton and H. R. Hind , The total chromatic number of graphs having large maximum degree, Discrete Math. 117(1–3) (1993) 127–140. Crossref, Google Scholar
8. W. Imrich and S. Klavžar , Product Graphs: Structure and Recognition (Wiley, New York, 2000). Google Scholar
9. J. Janssen and K. MacKeigan , Total colorings of direct product graphs, Contrib. Discrete Math. 15(1) (2020) 67–71. Crossref, Google Scholar
10. A. Kemnitz and M. Marangio , Total colorings of Cartesian products of graphs, Congr. Numer. 165 (2003) 99–110. Google Scholar
11. S. Mohan, J. Geetha and K. Somasundaram , Total coloring of Certain classes of product graphs, Electron. Notes Discrete Math. 53 (2016) 173–180. Crossref, Google Scholar
12. K. Pranavar and B. Zmazek , On total chromatic number of direct product graphs, J. Appl. Math. Comput. 33(1–2) (2010) 449–457. Crossref, Google Scholar
13. A. Snchez-Arroyo , Determining the total colouring number is NP-hard, Discrete Math. 78(3) (1989) 315–319. Crossref, Google Scholar
14. T. P. Sandhiya, J. Geetha and K. Somasundaram , Total coloring of certain classes of lexicographic product graphs, Discrete Math. Algorithms Appl. 14(3) (2021) 2150129. Link, Google Scholar
15. M. A. Seoud , Total colorings of Cartesian products, Int. J. Math. Educ. Sci. Technol. 28(4) (1997) 481–487. Crossref, Google Scholar
16. R. Vignesh, J. Geetha and K. Somasundaram , Total coloring conjecture for certain classes of graphs, Algorithms 11(10) (2018) 161. Crossref, Google Scholar
17. V. G. Vizing, Some unsolved problems in graph theory (in Russian), Uspekhi Mat. Nauk. 23(6) (1968) 117–134; English translation in Russ. Math. Surv. 23 (1968) 125–141. Google Scholar
18. H. P. Yap , Total Colourings of Graphs, Lecture Notes in Mathematics, Vol. 1623 (Springer, Berlin, 1996). Crossref, Google Scholar
19. H. P. Yap and K. H. Chew , Total Chromatic number of graphs of high degree, II, J. Aust. Math. Soc. 53(2) (1992) 219–228. Crossref, Google Scholar
20. B. Zmazek and J. Žerovnik , Behzad–Vizing conjecture and Cartesian product graphs, Appl. Math. Lett. 15(6) (2002) 781–784. Crossref, Google Scholar