The Total Chromatic Number of Complete Multipartite Graphs with Low Deficiency

被引：4
|
作者：
Dalal, Aseem [1 ]
Rodger, C. A. [2 ]
机构：
[1] Indian Inst Technol, Dept Math, Delhi 110016, India
[2] Auburn Univ, Dept Math & Stat, Auburn, AL 36849 USA
来源：
GRAPHS AND COMBINATORICS | 2015年 / 31卷 / 06期
关键词：
Total chromatic number; Type one; Complete multipartite graphs; COLORINGS;
D O I：
10.1007/s00373-014-1503-4
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
It has long been conjectured that the total chromatic number. chi '' (K) of the complete p-partite graph K = K(r(1),..., r(p)) is Delta (K)+ 1 if and only if both K not equal K-r,K- r and | V(K)| = 0 (mod 2) implies that Sigma(v is an element of V)(K)( (K) -d(K) (v)) is at least the number of parts of odd size. It is known that. chi '' (K) <=Delta (K)+ 2. In this paper, a new approach is introduced to attack the conjecture that makes use of amalgamations of graphs. The power of this approach is demonstrated by settling the conjecture for all complete 5-partite graphs.
引用
收藏
页码：2159 / 2173
页数：15
相关论文
共 50 条
  • [1] The Total Chromatic Number of Complete Multipartite Graphs with Low Deficiency
    Aseem Dalal
    C. A. Rodger
    Graphs and Combinatorics, 2015, 31 : 2159 - 2173
  • [2] Some Chromatic Equivalence Classes of Complete Multipartite Graphs
    Lau, Gee-Choon
    Zhao, Haixing
    UTILITAS MATHEMATICA, 2017, 105 : 75 - 85
  • [3] Total colorings of complete multipartite graphs using amalgamations
    Dalal, Aseem
    Panda, B. S.
    Rodger, C. A.
    DISCRETE APPLIED MATHEMATICS, 2024, 359 : 186 - 195
  • [4] On the total chromatic edge stability number and the total chromatic subdivision number of graphs
    Kemnitz, Arnfried
    Marangio, Massimiliano
    DISCRETE MATHEMATICS LETTERS, 2022, 10 : 1 - 8
  • [5] THE TOTAL CHROMATIC NUMBER OF SOME GRAPHS
    张忠辅
    张建勋
    王建方
    Science China Mathematics, 1988, (12) : 1434 - 1441
  • [6] Total chromatic number of generalized Mycielski graphs
    Chen, Meirun
    Guo, Xiaofeng
    Li, Hao
    Zhang, Lianzhu
    DISCRETE MATHEMATICS, 2014, 334 : 48 - 51
  • [7] On the double total dominator chromatic number of graphs
    Beggas, Fairouz
    Kheddouci, Hamamache
    Marweni, Walid
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2022, 14 (05)
  • [8] On total chromatic number of direct product graphs
    Prnaver K.
    Zmazek B.
    Journal of Applied Mathematics and Computing, 2010, 33 (1-2) : 449 - 457
  • [9] Total-colorings of complete multipartite graphs using amalgamations
    Dalal, Aseem
    Panda, B. S.
    Rodger, C. A.
    DISCRETE MATHEMATICS, 2016, 339 (05) : 1587 - 1592
  • [10] The Adjacent Vertex Distinguishing Total Chromatic Number of Graphs
    Wang, Zhiwen
    Zhu, Enqiang
    2010 4TH INTERNATIONAL CONFERENCE ON BIOINFORMATICS AND BIOMEDICAL ENGINEERING (ICBBE 2010), 2010,
12345