Recent results on the total chromatic number.

*(English)*Zbl 0793.05059The total chromatic number \(\chi_ T(G)\) of a graph \(G\) is the least number of colours needed to colour the vertices and edges of \(G\) so that no two adjacent or incident elements receive the same colour. In 1965, M. Behzad and V. G. Vizing independently made the following conjecture (known as the Total Colouring Conjecture, abbreviated as TCC): For any simple graph \(G\), \(\Delta(G)+ 1\leq \chi_ T(G)\leq \Delta(G)+ 2\), where \(\Delta(G)\) is the maximum (vertex) degree of \(G\).

Very strong evidence for the truth of the TCC has recently been provided by C. McDiarmid and B. Reed [J. Comb. Theory, Ser. B 57, No. 1, 122-130 (1993; Zbl 0760.05043)], who showed that the proportion of graphs of order \(n\) with \(\chi_ T(G)> \Delta(G)+ 2\) is \(o(c^{n^ 2})\) for some \(c\in (0,1)\).

This paper gives a survey mainly on three types of recent results on the the total chromatic number.

1. Upper bounds for \(\chi_ T(G)\): A. G. Chetwynd, R. Häggkrist, H. Hind, C. J. H. McDiarmid, B. Reed and A. Sànchez-Arroyo have obtained several upper bounds for the total chromatic number of a graph \(G\).

2. The TCC is true for graphs of high degree: The TCC had been proved for graphs having maximum degree at most five in the 1970’s. Recently, it has been proved for graphs \(G\) having \(\Delta(G)\geq | V(G)|- 5\) (the reviewer et al.) and for graphs \(G\) having \(\Delta(G)\geq {3\over 4}| V(G)|\) (the author and H. Hind).

3. The exact total chromatic number of graphs of high degree: The exact value of \(\chi_ T(G)\) for graphs \(G\) having \(\Delta(G)\geq | G|- 2\) has been determined by B. L. Chen, H. L. Fu, the author and the reviewer.

Very strong evidence for the truth of the TCC has recently been provided by C. McDiarmid and B. Reed [J. Comb. Theory, Ser. B 57, No. 1, 122-130 (1993; Zbl 0760.05043)], who showed that the proportion of graphs of order \(n\) with \(\chi_ T(G)> \Delta(G)+ 2\) is \(o(c^{n^ 2})\) for some \(c\in (0,1)\).

This paper gives a survey mainly on three types of recent results on the the total chromatic number.

1. Upper bounds for \(\chi_ T(G)\): A. G. Chetwynd, R. Häggkrist, H. Hind, C. J. H. McDiarmid, B. Reed and A. Sànchez-Arroyo have obtained several upper bounds for the total chromatic number of a graph \(G\).

2. The TCC is true for graphs of high degree: The TCC had been proved for graphs having maximum degree at most five in the 1970’s. Recently, it has been proved for graphs \(G\) having \(\Delta(G)\geq | V(G)|- 5\) (the reviewer et al.) and for graphs \(G\) having \(\Delta(G)\geq {3\over 4}| V(G)|\) (the author and H. Hind).

3. The exact total chromatic number of graphs of high degree: The exact value of \(\chi_ T(G)\) for graphs \(G\) having \(\Delta(G)\geq | G|- 2\) has been determined by B. L. Chen, H. L. Fu, the author and the reviewer.

Reviewer: H.P.Yap (Singapore)

PDF
BibTeX
Cite

\textit{A. J. W. Hilton}, Discrete Math. 111, No. 1--3, 323--331 (1993; Zbl 0793.05059)

Full Text:
DOI

##### References:

[1] | Behzad, M., Graphs and their chromatic numbers, () · Zbl 0217.30904 |

[2] | Berge, C., Graphs and hypergraphs, (1973), North-Holland Amsterdam · Zbl 0483.05029 |

[3] | Chen, Bor-Liang; Fu, Hung-Lin, The total colouring of graphs of order 2n and maximum degree 2n-2, Graphs combin., 8, 119-123, (1992) · Zbl 0771.05034 |

[4] | Chetwynd, A.G., Total colourings of graphs, () · Zbl 0840.05024 |

[5] | A.G. Chetwynd and R. Häggkvist, Some upper bounds on the total and list chromatic numbers of multigraphs, submitted. · Zbl 0814.05038 |

[6] | Chetwynd, A.G.; Hilton, A.J.W., Star multigraphs with three vertices of maximum degree, Math. proc. Cambridge philos. soc., 100, 303-317, (1986) · Zbl 0619.05023 |

[7] | Chetwynd, A.G.; Hilton, A.J.W., Some refinements of the total chromatic number conjecture, Congr. numer., 66, 195-215, (1988) · Zbl 0677.05026 |

[8] | Chetwynd, A.G.; Hilton, A.J.W., 1-factorizing regular graphs of high degree - an improved bound, Discrete math., 75, 103-112, (1989) · Zbl 0675.05030 |

[9] | Chetwynd, A.G.; Hilton, A.J.W., The edge-chromatic class of graphs with maximum degree of least ⋎V(G)⋎ -3, Ann. discrete math., 41, 91-100, (1989) · Zbl 0692.05032 |

[10] | 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 |

[11] | 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 |

[12] | Chvátal, V., On Hamilton’s ideals, J. combin. theory ser. B, 12, 163-168, (1972) · Zbl 0213.50803 |

[13] | J.K. Dugdale and A.J.W. Hilton, The total chromatic number of regular graphs whose complement is bipartie, Discrete Math., to appear. · Zbl 0794.05028 |

[14] | Flandrin, E.; Jung, H.A.; Li, H., Hamiltonism, degree sums and neighbourhood intersections, Discrete math., 90, 41-52, (1991) · Zbl 0746.05038 |

[15] | Fournier, J.-C., Méthode et théorème générale de coloration des arêtes d’un multigraphe, J. math. pures appl., 56, 437-453, (1977) · Zbl 0326.05103 |

[16] | Ghouila-Houri, A., Une condition suffisante d’existence d’un circuit hamiltonien, C.R. acad. sci., 251, 494, (1960) · Zbl 0091.37503 |

[17] | Hajnal, A.; Szemerédi, E., Proof of a conjecture of erdős, (), 601-623, Colloq. Math. Soc. János Bolyai |

[18] | Hilton, A.J.W., Recent progress in edge-colouring graphs, Discrete math., 64, 303-307, (1987) · Zbl 0622.05021 |

[19] | Hilton, A.J.W., Two conjectures on edge-colouring, Discrete math., 74, 61-64, (1989) · Zbl 0677.05025 |

[20] | Hilton, A.J.W., A total chromatic number analogue of Plantholt’s theorem, Discrete math., 79, 169-175, (1989/90) · Zbl 0714.05025 |

[21] | Hilton, A.J.W., The total chromatic number of nearly complete bipartite graphs, J. combin. theory ser. B, 52, 9-19, (1991) · Zbl 0743.05022 |

[22] | A.J.W. Hilton, Star multigraphs with r vertices of maximum degree, submitted. |

[23] | A.J.W. Hilton and H.R.F. Hind, Total chromatic number of graphs having large maximum degree, Discrete Math., to appear. · Zbl 0785.05035 |

[24] | Hilton, A.J.W.; Cheng, Zhao, The relationship between an edge-colouring conjecture and a total colouring conjecture, J. combin. math. combin. comput., 10, 83-95, (1991) · Zbl 0741.05030 |

[25] | Hind, H.R.F., An upper bound for the total chromatic number, Graphs combin, 6, 153-159, (1990) · Zbl 0725.05043 |

[26] | Hind, H.R.F., An upper bound for the total chromatic number of dense graphs, J. graph theory, 16, 197-202, (1992) · Zbl 0767.05048 |

[27] | Hoffman, D.G.; Rodger, C.A., The chromatic index of complete partite graphs, J. graph theory, 16, 159-163, (1992) · Zbl 0760.05041 |

[28] | McDiarmid, C.J.H., Colourings of random graphs, (), Pitman Research Notes in Mathematics · Zbl 0298.05134 |

[29] | C.J.H. McDiarmid and B. Reed, On total colourings of graphs, J. Combin. Theory Ser. B, to appear. · Zbl 0725.05036 |

[30] | C.J.H. McDiarmid and A. Sanchez-Arroyo, Total colouring regular bipartite graphs is NP-hard, submitted. · Zbl 0791.05042 |

[31] | Niessen, T.; Volkmann, L., Class 1 conditions depending on the minimum degree and the number of vertices of maximum degree, J. graph theory, 14, 225-246, (1990) · Zbl 0704.05041 |

[32] | Ryser, H.J., A combinatorial theorem with an application to Latin rectangles, Proc. amer. math. soc., 2, 550-552, (1951) · Zbl 0043.01202 |

[33] | Sánchez-Arroyo, A., Determining the total colouring number is NP-hard, Discrete math., 78, 315-319, (1989) · Zbl 0695.05023 |

[34] | Vizing, V.G., On an estimate of the chromatic class of a p-graph, Diskret analiz., 3, 25-30, (1964), (in Russian) |

[35] | Yap, H.P.; Jian-Fang, Wang; Zhongfu, Zhang, Total chromatic number of graphs of high degree, J. austral. math. soc. ser. A, 1434-1441, (1988) · Zbl 0664.05017 |

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.