zbMATH — the first resource for mathematics

The total chromatic number of regular graphs whose complement is bipartite. (English) Zbl 0794.05028
Given a graph \(G= (V,E)\), a total coloring of \(G\) is an assignment of colors to the elements of \(V\cup E\) in such a way that no two adjacent or incident elements receive the same color. The total chromatic number \(\chi''(G)\) is the least number of colors in a total coloring of \(G\). There is an almost 30-years-old conjecture that for a simple graph \(G\) we have \(\Delta+ 1\leq \chi''(G)\leq \Delta+ 2\), where \(\Delta\) is the maximum vertex degree of \(G\). If \(\chi''(G)= \Delta+ 1\) then graph \(G\) is type 1 and if \(\chi''(G)= \Delta+ 2\) then \(G\) is type 2. Deciding the type of \(G\) is NP-complete. In the paper the authors prove the following theorem:
Let \(G\) be a regular simple graph of even order \(2n\geq 6\) such that \(\overline G\) is bipartite. Then \(G\) is of type 1 if and only if: (i) \(G\neq K_{2n}\) and (ii) \(\overline G\neq K_{n,n}\) when \(n\) is even.
Reviewer: M.Kubale (Gdańsk)

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] L.D. Andersen and E. Mendelsohn, 1-factorization of K_{2n} with given edges in distinct 1-factors, in preparation.
[2] Ash, P., Cycles in graphs, ()
[3] Behzad, M., Graphs and their chromatic numbers, () · Zbl 0217.30904
[4] Chetwynd, A.G.; Häggkvist, R., (), preprint
[5] Chetwynd, A.G.; Hilton, A.J.W., Some refinements of the total chromatic number conjecture, Congr. numer., 66, 195-216, (1988) · Zbl 0677.05026
[6] A.G. Chetwynd, A.J.W. Hilton and Zhao Cheng, On the total chromatic number of graphs of high minimum degree, J. London Math. Soc., to appear. · Zbl 0753.05033
[7] Dugdale, J.K.; Hilton, A.J.W., The total chromatic number of regular graphs of order 2n and degree 2n-3, J. combin. inform. system sci., 15, 103-110, (1990) · Zbl 0742.05040
[8] Ghouila-Houri, A., Une condition suffisante d’existence d’un circuit hamiltonien, C.R. acad. sci., 251, 494, (1960) · Zbl 0091.37503
[9] Hartman, A., Partial triple systems and edge-colourings, Discrete math., 62, 183-196, (1986) · Zbl 0656.05016
[10] Hilton, A.J.W., Recent results on the total chromatic number, Discrete math., 111, 323-331, (1993) · Zbl 0793.05059
[11] A.J.W. Hilton, Alternating Hamilton cycles in regular edge-coloured bipartite graphs, Discrete Appl. Math., to appear. · Zbl 0751.05066
[12] Hilton, A.J.W., A total chromatic number analogue of Plantholt’s theorem, Discrete math., 79, 169-175, (1989/90) · Zbl 0714.05025
[13] Hilton, A.J.W.; Hind, H.R., The total chromatic number of graphs having large maximum degree, Discrete math., 117, 127-140, (1993) · Zbl 0785.05035
[14] Hilton, A.J.W.; Cheng, Zhao, On the relationship between an edge colouring conjecture and a total colouring conjecture, J. combin. math. combin. comput., 10, 83-95, (1991) · Zbl 0741.05030
[15] Hind, H.R., An upper bound for the total chromatic number, Graphs combin., 6, 153-159, (1990) · Zbl 0725.05043
[16] König, D., Theorie der endlichen und unendlichen graphen, (1950), Chelsea New York · Zbl 0040.10303
[17] Kostochka, A.V., The total colouring of a multigraph with maximal degree 4, Discrete math., 17, 161-163, (1977) · Zbl 0411.05038
[18] Nash Williams, C.St.J.A., Hamilton circuits in graphs and digraphs, (), 237-243 · Zbl 0195.25902
[19] Vizing, V.G., Some unsolved problems in graph theory, Uspekhi math. 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.