آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 123 |
| تعداد مقالات | 1,567 |
| تعداد مشاهده مقاله | 1,694,939 |
| تعداد دریافت فایل اصل مقاله | 1,578,260 |
Total Chromatic Number for Certain Classes of Lexicographic Product Graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 5، دوره 9، شماره 2، شهریور 2024، صفحه 233-240 اصل مقاله (658.34 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2022.27736.1333 | ||
| نویسندگان | ||
| T.P. Sandhiya* ؛ J. Geetha؛ K. Somasundaram | ||
| Department of Mathematics, Amrita School of Physical Sciences - Coimbatore, Amrita Vishwa Vidyapeetham, India | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| Total coloring؛ Lexicographic Product؛ Deleted Lexicographic Product | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 1,022 تعداد دریافت فایل اصل مقاله: 2,527 |
||