# 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)

##### MSC:
 05C15 Coloring of graphs and hypergraphs
Full Text:
##### References:
  L.D. Andersen and E. Mendelsohn, 1-factorization of K_{2n} with given edges in distinct 1-factors, in preparation.  Ash, P., Cycles in graphs, ()  Behzad, M., Graphs and their chromatic numbers, () · Zbl 0217.30904  Chetwynd, A.G.; Häggkvist, R., (), preprint  Chetwynd, A.G.; Hilton, A.J.W., Some refinements of the total chromatic number conjecture, Congr. numer., 66, 195-216, (1988) · Zbl 0677.05026  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  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  Ghouila-Houri, A., Une condition suffisante d’existence d’un circuit hamiltonien, C.R. acad. sci., 251, 494, (1960) · Zbl 0091.37503  Hartman, A., Partial triple systems and edge-colourings, Discrete math., 62, 183-196, (1986) · Zbl 0656.05016  Hilton, A.J.W., Recent results on the total chromatic number, Discrete math., 111, 323-331, (1993) · Zbl 0793.05059  A.J.W. Hilton, Alternating Hamilton cycles in regular edge-coloured bipartite graphs, Discrete Appl. Math., to appear. · Zbl 0751.05066  Hilton, A.J.W., A total chromatic number analogue of Plantholt’s theorem, Discrete math., 79, 169-175, (1989/90) · Zbl 0714.05025  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  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  Hind, H.R., An upper bound for the total chromatic number, Graphs combin., 6, 153-159, (1990) · Zbl 0725.05043  König, D., Theorie der endlichen und unendlichen graphen, (1950), Chelsea New York · Zbl 0040.10303  Kostochka, A.V., The total colouring of a multigraph with maximal degree 4, Discrete math., 17, 161-163, (1977) · Zbl 0411.05038  Nash Williams, C.St.J.A., Hamilton circuits in graphs and digraphs, (), 237-243 · Zbl 0195.25902  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.