zbMATH — the first resource for mathematics

Total colorings of graphs of order \(2n\) having maximum degree \(2n-2\). (English) Zbl 0771.05034
Summary: Let \(\chi_ t(G)\) and \(\Delta(G)\) denote respectively the total chromatic number and maximum degree of graph \(G\). H. P. Yap, J.-F. Wang and Z. Zhang [J. Aust. Math. Soc., Ser. A 47, No. 3, 445-452 (1989; Zbl 0702.05032)] proved that if \(G\) is a graph of order \(p\) having \(\Delta(G)\geq p-4\), then \(\chi_ t(G)\leq\Delta(G)+2\). Hilton has characterized the class of graphs \(G\) of order \(2n\) having \(\Delta(G)=2n-1\) such that \(\chi_ t(G)=\Delta(G)+2\). In this paper, we characterize the class of graphs \(G\) of order \(2n\) having \(\Delta(G)=2n- 2\) such that \(\chi_ t(G)=\Delta(G)+2\).

05C15 Coloring of graphs and hypergraphs
05C75 Structural characterization of families of graphs
Full Text: DOI
[1] Andersen, L.D., Mendelsohn, E.: 1-factorizations ofK 2m with given edges in distinct 1-factors. University Center of Aalborg (1985) (preprint)
[2] Behzad, M., Chartrand, G., Cooper, J.: The colouring numbers of complete graphs. J. London Math. Soc.42, 226–228 (1967) · Zbl 0152.41203
[3] Bondy, J.A., Murty, U.S.R.: Graph theory with applications. Elsevier North Holland, Inc., 1976 · Zbl 1226.05083
[4] Chetwynd, A.G., Hilton, A.J.W.: Some refinements of the total chromatic number cojecture. Congressus Numerantium66, 195–216 (1988) · Zbl 0677.05026
[5] Hilton, A.J.W.: A total-chromatic number analogue of Plenatholt’s theorem. Discrete Math.79, 169–175 (1989/90) · Zbl 0714.05025
[6] Kostachka, A.V.: The total coloring of multigraph with maximal degree 4. Discrete Math.17, 161–163 (1977) · Zbl 0411.05038
[7] Rosenfeld, M.: On the total coloring of certain graphs. Israel J. Math.,9(3), 396–402 (1971) · Zbl 0211.56604
[8] Vizing, V.G.: On an estimate of the chromatic class of ap-graph (Russian)., Diskret. Analiz3, 25–30 (1964)
[9] Yap, H.P. Total colourings of graphs. Bull. London Math. Soc.21, 159–163 (1989) · Zbl 0636.05025
[10] Yap, H.P. Wang Jian-Fang Zhang Zhongfu: Total chromatic number of graph of high degree. J. Aust. Math. Soc. (Series A)47, 445–452 (1989)
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.