A New Proof of a Characterization of \((k,l)\)-Colourable Chordal Graphs

Dennis D.A. Epple1
1University of Victoria, PO BOX 3060 STN CSC, Victoria, B.C., V8W 3R4, Canada;

Abstract

A graph is \((k, l)\)-colorable if its vertex set can be partitioned into \( k \) independent sets and \( l \) cliques. A graph is chordal if it does not contain any induced cycle of length at least four. A theorem by Hell et al. states that a chordal graph is \((k, l)\)-colorable if and only if it does not contain \((l+1)K_{k+1}\) as an induced subgraph. Presented here is a short alternative proof of this result, using the characterization of chordal graphs via perfect elimination orderings.