zbMATH — the first resource for mathematics

The total chromatic number of graphs having large maximum degree. (English) Zbl 0785.05035
A total-colouring \(\theta\) of a graph \(G\) is a mapping from \(V(G)\cup E(G)\) to a set \(\mathcal C\) such that no two adjacent or incident elements have the same image. The minimum cardinality of \(\mathcal C\) for which there exists a total-colouring \(\theta: V(G)\cup E(G)\to{\mathcal C}\) is called the total chromatic number of \(G\), and is denoted by \(\chi''(G)\).
For simple finite graphs \(G\), it is obvious that \(\chi''(G)\geq \Delta(G)+1\), where \(\Delta(G)\) is the maximum degree of \(G\). M. Behzad and V. G. Vizing conjectured in 1965 that for any finite simple graph \(G\), \(\chi''(G)\leq \Delta(G)+2\). This conjecture is known as the Total Colouring Conjecture (TCC).
It was proven that the TCC holds for graphs of low maximum degree in the 70’s. Very recently the TCC was proved for graphs \(G\)
(i) having \(\Delta(G)\geq | G|-4\) by H. P. Yap, Wang Jian-Fang and Zhang Zhongfu [J. Aust. Math. Soc., Ser. A 47, No. 3, 445-452 (1989; Zbl 0702.05032)];
(ii) having \(\Delta(G)\geq | G|-5\) by H. P. Yap and K. H. Chew [J. Aust. Math. Soc., Ser. A 53, No. 2, 219-228 (1992; Zbl 0768.05043)];
(iii) having even order and minimum degree \(\delta(G)\geq{3\over 4} | G|\) by A. G. Chetwynd, A. J. W. Hilton and Zhao Cheng [J. Lond. Math. Soc., II. Ser. 44, No. 2, 193-202 (1991; Zbl 0753.05033)] and having odd order with \(\delta(G)\geq {3\over 4} | G|\) by K. H. Chew and H. P. Yap (unpublished).
The present authors prove that the TCC holds for graphs \(G\) having \(\Delta(G)\geq{3\over 4} | G|\). This is a refinement of (iii) and it supersedes (ii) when \(| G|\geq 20\). The reviewer belives that this is the most important result obtained so far in the area of total colourings of graphs because it confirms that the TCC is true for one quarter of all graphs.

05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
Full Text: DOI
[1] Behzad, M., Graphs and their chromatic numbers, () · Zbl 0217.30904
[2] Behzad, M.; Chartrand, G.; Cooper, J.K., The colour numbers of complete graphs, J. London math. soc., 42, 225-228, (1967) · Zbl 0152.41203
[3] Bollobás, B., Extremal graph theory, (1978), Academic Press London · Zbl 0419.05031
[4] Bollobás, B., Graph theory: an introductory course, (1979), Springer New York · Zbl 0411.05032
[5] Chetwynd, A.G., Total colourings of graphs, (), 65-77 · Zbl 0840.05024
[6] Chetwynd, A.G.; Hilton, A.J.W., The edge-chromatic class of graphs with large maximum degree, where the number of vertices of maximum degree is relatively small, J. combin. theory ser. B, 48, 45-66, (1990) · Zbl 0716.05021
[7] Chetwynd, A.G.; Hilton, A.J.W.; Cheng, Zhao, The total chromatic number of graphs of high minimum degree, J. London math. soc., 44, 2, 193-202, (1991) · Zbl 0753.05033
[8] Flandrin, E.; Jung, H.A.; Li, H., Hamiltonism, degree sums and neighborhood conditions, Discrete math., 90, 41-52, (1991) · Zbl 0746.05038
[9] Hajnal, A.; Szemerédi, E., Proof of a conjecture of P. erdős, (), 601-623
[10] Hind, H.R., An upper bound for the total chromatic number, Graphs and combin., 6, 153-159, (1990) · Zbl 0725.05043
[11] Hind, H.R., An upper bound for the total chromatic number of dense graphs, J. graph theory, 16, 197-202, (1992) · Zbl 0767.05048
[12] Kostochka, A.V., The total colouring of a multigraph with maximal degree 4, Discrete math., 17, 161-163, (1977) · Zbl 0411.05038
[13] Kostochka, A.V., An analogue of Shannon’s estimate for complete colorings (Russian), Diskret. analiz., 30, 13-22, (1977) · Zbl 0424.05026
[14] Kostochka, A.V., Exact upper bound for the total chromatic number of a graph (Russian), Theorie der graphen und netwerke, 33-36, (1979), Proc. 24th Int. Wiss. Koll. TH Ilmenau Vortrasgreine
[15] Rosenfeld, M., On the total coloring of certain graphs, Israel J. math., 9, 396-402, (1971) · Zbl 0211.56604
[16] Sanchez-Arroyo, A., Determining the total chromatic number is NP-hard, Discrete math., 78, 315-319, (1989) · Zbl 0695.05023
[17] Vijayaditya, N., On total chromatic number of graph, J. London math. soc., 3, 2, 405-408, (1971) · Zbl 0223.05103
[18] Vizing, V.G., On an estimate of the chromatic class of a p-graph (Russian), Diskret. analiz., 3, 23-30, (1964)
[19] Vizing, V.G., Some unsolved problems in graph theory, Russian math. surveys, 23, 125-141, (1968) · Zbl 0192.60502
[20] Yap, H.P., On the total chromatic number of a graph, Research report no. 343, (1988) · Zbl 0685.05036
[21] H.P. Yap, Wang Jian-Fang and Zhang Zhongfu, Total chromatic number of graphs of high degree, J. Australian Math. Soc., to appear. · Zbl 0702.05032
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.