×

The total chromatic number of any multigraph with maximum degree five is at most seven. (English) Zbl 0871.05023

Summary: The result announced in the title is proved. A new proof of the total 6-colorability of any multigraph with maximum degree 4 is also given.

MSC:

05C15 Coloring of graphs and hypergraphs
05C99 Graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Behzad, M., The total chromatic number of a graph: a survey, (Welsh, D. J.A., Mathematics and its Applications. Mathematics and its Applications, Proc. Conf. Oxford (1969), Academic Press: Academic Press New York), 1-9, 1971
[2] Borodin, O. V., On partition of graphs into degenerate subgraphs, Methods of Discrete Analysis in the Theory of Graphs and Logical Functions, 28, 3-11 (1976), (in Russian) · Zbl 0425.05058
[3] Borodin, O. V., On the total coloring of planar graphs, J. Reine Angew. Math., 394, 180-185 (1989) · Zbl 0653.05029
[4] Chetwynd, A.; Häggkvist, R., Some upper bounds on the total and list chromatic numbers of multigraphs, J. Graph Theory, 16, 503-516 (1992) · Zbl 0814.05038
[5] Chetwynd, A.; Häggkvist, R., An improvement of Hind’s upper bound on the total chromatic number, (Research Report No 9 (1993), Univ. of Umea: Univ. of Umea Sweden) · Zbl 0862.05039
[6] Hind, H., An upper bound for the total chromatic number, Graphs Combin., 6, 153-160 (1990) · Zbl 0725.05043
[7] Kostochka, A. V., The total coloring of a multigraph with maximal degree 4, Discrete Math., 17, 161-163 (1977) · Zbl 0411.05038
[8] Kostochka, A. V., An analog of the Shannon bound for total coloring, Methods of Discrete Analysis in the Solution of Combinatorial Problems, 30, 13-22 (1977), (in Russian) · Zbl 0424.05026
[9] Kostochka, A. V., Upper bounds on chromatic functions of graphs, (Doct. Thesis (1978), Novosibirsk), (in Russian) · Zbl 0677.05027
[10] Kostochka, A. V., Exact upper bound on the total chromatic number of multigraphs, (Proceedings of the 24th Int. Sci. Colloq. of Tech. Univ. of Illmenau, vol. 5 (1979), Illmenau: Illmenau GDR), 33-36, (in Russian)
[11] Kronk, H. V.; Mitchem, J., Critical point-arboritic graphs, J. London Math. Soc., 9, 459-466 (1975), (Second Series) · Zbl 0298.05132
[12] Lovász, L.; Plummer, M. D., Matching Theory (1986), North-Holland: North-Holland Amsterdam · Zbl 0618.05001
[13] Petersen, J., Die Theorie der regularen Graphen, Acta Math., 15, 193-220 (1891) · JFM 23.0115.03
[14] Rosenfeld, M., On the total coloring of certain graphs, Israel J. Math., 9, 396-402 (1971) · Zbl 0211.56604
[15] Vijayaditya, W., On total coloring of a graph, J. London Math. Soc., 3, 405-408 (1971), (Second Series) · Zbl 0223.05103
[16] Vizing, V. G., Some unsolved problems in graph theory, Uspeki Mat. Nauk, 23, 117-134 (1968), (in Russian) · Zbl 0177.52301
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.