✦ LIBER ✦
Coloring graphs which have equibipartite complements
✍ Scribed by Hilton, A. J. W.; Zhao, C.
- Publisher
- John Wiley and Sons
- Year
- 1997
- Tongue
- English
- Weight
- 205 KB
- Volume
- 26
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
If G is a graph of order 2n ≥ 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 K n 's with n odd. Similarly if G is a graph of order 2n ≥ 6 whose complement Ḡ is equibipartite with bipartition (A, D), and if both Ḡ 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).