Total colorings of equibipartite graphs (Q1297471): Difference between revisions

The total chromatic number \(\chi_T(G)\) of a (simple) graph \(G\) is the least number of colours needed to colour the vertices and edges of \(G\) such that no two adjacent or incident vertices/edges receive the same colour. It is known that if \(G\) is a bipartite graph, then \(\Delta(G)+ 1\leq\chi_T(G)\leq \Delta(G)+ 2\), where \(\Delta(G)\) is the maximum degree of \(G\). A counterexample to a conjecture of \textit{A. G. Chetwynd} and \textit{A. J. W. Hilton} [Congr. Numerantium 66, 195-216 (1988; Zbl 0677.05026)] which claims that an equibipartite graph \(G\) has \(\chi_T(G)= \Delta(G)+ 1\) if and only if \(G\) is biconformable was produced by \textit{B. L. Chen}, \textit{C. K. Cheng}, \textit{H. L. Fu} and \textit{K. C. Huang} [Discrete Math. 184, 49-60 (1998)]. The counterexample is an equibipartite graph \(G\) of order \(2n\) with \(\Delta(G)= n-1\). In the same paper, Chen et al. also made the following conjecture: Suppose \(J\) is a subgraph of the complete bipartite graph \(K_{n,n}\) such that \(G= K_{n,n}- E(J)\) is \((n-2)\)-regular, where \(n\geq 5\). Then \(\chi_T(G)= n-1\) if and only if \(J\) contains a 4-cycle. Adopting an elegant method suggested by the reviewer of this paper, the present four authors succeeded in proving this conjecture in this paper.