×

zbMATH — the first resource for mathematics

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Behzad, M., The total chromatic number of a graph: a survey, (), 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, () · 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, (), (in Russian) · Zbl 0677.05027
[10] Kostochka, A.V., Exact upper bound on the total chromatic number of multigraphs, (), 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 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.