Coloring graphs which have equibipartite complements
A. J. W. Hilton, Cheng Zhao · Journal of Graph Theory · 1997
If G is a graph of order $2n \geq 4$ with an equibipartite complement, then G is Class 1 (i.e., the chromatic index of G is Δ (G)) if and only if G is not the union of two disjoint Kn's with n odd. Similarly if G is a graph of order 2n ≥ 6 whose complement G is equibipartite with bipartition (A, D), and if both G and B, the induced bipartite subgraph of G with bipartition (A, D), have a 1-factor, then G is Type 1 (i.e., the total chromatic number of G is Δ (G) + 1). © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 183–194, 1997