Total chromatic number for certain classes of product graphs

被引：0
作者：
Sandhiya, T. P. [1 ]
Geetha, J. [1 ]
Somasundaram, K. [1 ]
机构：
[1] Amrita Sch Phys Sci, Dept Math, Amrita Vishwa Vidyapeetham, Coimbatore, India
来源：
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS | 2024年 / 16卷 / 07期
关键词：
Total coloring; direct product; strong product; lexicographic product; CONJECTURE; COLORINGS;
D O I：
10.1142/S1793830923500994
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
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 chi ''(G). Behzad-Vizing conjecture (Total Coloring Conjecture) states that for any graph G, chi ''(G) <= Delta(G) + 2, where Delta(G) is the maximum degree of G. In this paper, we verify the Behzad-Vizing conjecture for some product graphs.
引用
收藏
页数：8
相关论文
共 20 条
  • [1] Behzad M., 1965, Graphs and their Chromatic Numbers
  • [2] Colorings of plane graphs: A survey
    Borodin, O. V.
    [J]. DISCRETE MATHEMATICS, 2013, 313 (04) : 517 - 539
  • [3] On total coloring the direct product of cycles and bipartite direct product of graphs
    Castonguay, D.
    de Figueiredo, C. M. H.
    Kowada, L. A. B.
    Patrao, C. S. R.
    Sasaki, D.
    [J]. DISCRETE MATHEMATICS, 2023, 346 (06)
  • [4] On total coloring the direct product of complete graphs
    Castonguay, D.
    de Figueiredo, C. M. H.
    Kowada, L. A. B.
    Patrao, C. S. R.
    Sasaki, D.
    Valencia-Pabon, M.
    [J]. PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, 2021, 195 : 306 - 314
  • [5] Total Colorings of Product Graphs
    Geetha, J.
    Somasundaram, K.
    [J]. GRAPHS AND COMBINATORICS, 2018, 34 (02) : 339 - 347
  • [6] GEETHA J, 2023, AKCEINT J GRAPHS COM, P1
  • [7] THE TOTAL CHROMATIC NUMBER OF GRAPHS HAVING LARGE MAXIMUM DEGREE
    HILTON, AJW
    HIND, HR
    [J]. DISCRETE MATHEMATICS, 1993, 117 (1-3) : 127 - 140
  • [8] Imrich W., 2000, WIL INT S D
  • [9] Kemnitz A., 2003, C NUMER, V165, P99
  • [10] Mackeigan K, 2020, CONTRIB DISCRET MATH, V15, P67
12