Abstract | ||
---|---|---|
It has long been conjectured that the total chromatic number \( \chi ^{\prime \prime }(K)\) of the complete \(p\)-partite graph \(K = K(r_1, \dots , r_p)\) is \(\Delta (K) + 1\) if and only if both \(K \ne K_{r,r}\) and \(|V(K)| \equiv \)0 (mod 2) implies that \(\Sigma _{v \in V(K)}(\Delta (K) - d_K(v))\) is at least the number of parts of odd size. It is known that \(\chi ^{\prime \prime }(K) \le \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. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1007/s00373-014-1503-4 | Graphs and Combinatorics |
Keywords | Field | DocType |
Total chromatic number, Type one, Complete multipartite graphs | Prime (order theory),Graph,Combinatorics,Multipartite,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
31 | 6 | 1435-5914 |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Aseem Dalal | 1 | 3 | 1.53 |
C. A. Rodger | 2 | 189 | 35.61 |