Total Chromatic Number for Certain Classes of Lexicographic Product Graphs

Document Type : Original paper

Authors

Department of Mathematics, Amrita School of Physical Sciences - Coimbatore, Amrita Vishwa Vidyapeetham, India

Abstract

A total coloring of a graph $G$ is an assignment of colors to all the elements (vertices and edges) of the graph in such a way that no two adjacent or incident elements receive the same color. The total chromatic number of $G$, denoted by $\chi''(G)$, is the minimum number of colors which need for total coloring of $G$. The Total Coloring Conjecture (TCC) made independently by Behzad and Vizing which claims that, $\Delta(G)+1 \leq \chi''(G) \leq \Delta(G)+2 $, where $\Delta(G)$ is the maximum degree of $G$. The lower bound is sharp and the upper bound remains to be proved. In this paper, we prove the TCC for certain classes of lexicographic and deleted lexicographic products of graphs. Also, we obtained the lower bound for certain classes of these products.

Keywords

Main Subjects

References

[1] M. Behzad, Graphs and their chromatic numbers, Ph.D. thesis, Michigan State University, 1965.
[2] 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
[3] J. Geetha, N. Narayanan, and K. Somasundaram, Total coloring- A survey, AKCE Int. J. Graphs Combin. 20 (2023), no. 3, 339–351. https://doi.org/10.1080/09728600.2023.2187960
[4] J. Geetha and K. Somasundaram, Total colorings of product graphs, Graphs Combin. 34 (2018), no. 2, 339–347. https://doi.org/10.1007/s00373-018-1876-x
[5] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition, Wiley, New york, 2000.
[6] C.J.H. McDiarmid and A. Sánchez-Arroyo, Total colouring regular bipartite graphs is NP-hard, Discrete Math. 124 (1994), no. 1-3, 155–162. https://doi.org/10.1016/0012-365X(92)00058-Y
[7] Š. Miklavič and M. Milanič, Equistable graphs, general partition graphs, triangle graphs, and graph products, Discrete Appl. Math. 159 (2011), no. 11, 1148–1159. https://doi.org/10.1016/j.dam.2011.03.011
[8] S. Mohan, J. Geetha, and K. Somasundaram, Total coloring of certain classes of product graphs, Electro. Notes Discrete Math. 53 (2016), 173–180. https://doi.org/10.1016/j.endm.2016.05.016
[9] A. Sánchez-Arroyo, Determining the total colouring number is NP-hard, Discrete Math. 78 (1989), no. 3, 315–319. https://doi.org/10.1016/0012-365X(89)90187-8
[10] T.P. Sandhiya, J. Geetha, and K. Somasundaram, Total colorings of certain classes of lexicographic product graphs, Discrete Math. Algorithms Appl. 14 (2022), no. 3, Article ID: 2150129. https://doi.org/10.1142/S1793830921501299
[11] R. Vignesh, J. Geetha, and K. Somasundaram, Total coloring conjecture for certain classes of graphs, Algorithms 11 (2018), no. 10, Article ID: 161. https://doi.org/10.3390/a11100161
[12] V.G. Vizing, Some unsolved problems in graph theory, Russian Math. Surveys 23 (1968), no. 6, Article ID: 125. https://doi.org/10.1070/RM1968v023n06ABEH001252
[13] H.P. Yap, Total Colourings of Graphs, Springer, Berlin, 1996.
Communications in Combinatorics and Optimization
Volume 9, Issue 2
June 2024
Pages 233-240

Files

Share

How to cite

Statistics