×

Total-colorings of complete multipartite graphs using amalgamations. (English) Zbl 1333.05104

Summary: This paper makes progress towards settling the long-standing conjecture that the total chromatic number \(\chi^{\prime\prime}\) of the complete \(p\)-partite graph \(K = K(r_1, \ldots, r_p)\) is \(\varDelta(K) + 1\) if and only if \(K \neq K_{r, r}\) and if \(K\) has an even number of vertices then \(\varSigma_{v \in V(K)}(\varDelta(K) - d_K(v))\) is at least the number of parts of odd size. Graphs of even order that are fairly close to being regular are the ones for which \(\chi^{\prime\prime}(K)\) remains in doubt. In this paper we show that \(K\) is of Type 1 if \(| V(K) |\) is even and \(r_2 < r_3\) (with parts arranged in non-decreasing order of size), thereby improving on the result of L. Dong and H. P. Yap [Bull. Inst. Comb. Appl. 28, 107–117 (2000; Zbl 0940.05026)]. Furthermore, it is shown using this result together with the novel approach of graph amalgamations that all complete multipartite graphs of the form \(K(r, r, \ldots, r, r + 1)\) are of Type 1.

MSC:

05C15 Coloring of graphs and hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Citations:

Zbl 0940.05026
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Behzad, M., Graphs and their Chromatic Numbers (1965), Michigan State University, (Doctoral thesis)
[2] Bermond, J.-C., Nombre chromatique total du graphe \(r\)-parti complete, J. Lond. Math. Soc., 9, 279-285 (1974), (in French) · Zbl 0293.05114
[3] Brinkmann, G.; Preissmann, M.; Sasaki, D., Snarks with total chromatic number 5, Discrete Math. Theor. Comput. Sci., 17, 369-382 (2015) · Zbl 1319.05048
[4] Bryant, D.; Horsley, D.; Maenhaut, B.; Smith, B. R., Cycle decompositions of complete multigraphs, J. Combin. Des., 19, 42-69 (2011) · Zbl 1205.05176
[5] Chetwynd, A. G.; Hilton, A. J.W., Some refinements of the totoal cohromatic number conjecture, Congr. Numer., 66, 195-215 (1988)
[6] Chew, K. H.; Yap, H. P., Total chromatic number of complete \(r\)-partite graphs, J. Graph Theory, 16, 629-634 (1992) · Zbl 0776.05044
[7] Dalal, A.; Rodger, C. A., The total chromatic number of complete multipartite graphs with low deficiency, Graphs Combin., 31, 2159-2173 (2015) · Zbl 1330.05062
[8] Dong, L.; Yap, H. P., The total chromatic number of unbalanced complete \(r\)-partite graphs of even order, Bull. Inst. Combin. Appl., 28, 107-117 (2000) · Zbl 0940.05026
[9] Hoffman, D. G.; Rodger, C. A., Class one graphs, J. Combin. Theory Ser. B, 44, 372-376 (1988) · Zbl 0659.05071
[10] Hoffman, D. G.; Rodger, C. A., The chromatic index of complete multipartite graphs, J. Graph Theory, 16, 159-163 (1992) · Zbl 0760.05041
[11] Hoffman, D. G.; Rodger, C. A., The total chromatic number of complete multipartite graphs, Festschrift for C. St. J. A. Nash-Williams, Congr. Numer., 113, 205-220 (1996) · Zbl 0977.05050
[12] Leach, C. D.; Rodger, C. A., Hamilton decompositions of complete graphs with a 3-factor leave, Discrete Math., 279, 337-344 (2004) · Zbl 1044.05058
[13] Machado, R. C.S.; de Figueiredo, C. M.H., Total chromatic number of unichord-free graphs, Discrete Appl. Math., 159, 1851-1864 (2011) · Zbl 1228.05157
[14] Vizing, V. G., Some unsolved problems in graph theory, Uspehi Mat. Nauk, 23, 117-134 (1968), (in Russian) · Zbl 0177.52301
[15] Xie, D.; Yang, W., The total chromatic number of graphs of even order and high degree, Discrete Math., 271, 295-302 (2003) · Zbl 1032.05056
[16] Xue, L.; Wu, J. L., Total chromatic number of planar graphs with few short cycles, J. Shandong Univ. Nat. Sci., 47, 84-87 (2012), (in Chinese) · Zbl 1274.05114
[17] Yap, H. P., Total colourings of graphs, Bull. Lond. Math. Soc., 21, 159-163 (1989) · Zbl 0636.05025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.