Coloring Bull-Free Perfectly Contractile Graphs
Benjamin Lévêque, Frédéric Maffray · SIAM Journal on Discrete Mathematics · 2008
We consider the class of graphs that contain no bull, no odd hole, and no antihole of length at least five. We present a new algorithm that colors optimally the vertices of every graph in this class. This algorithm is based on the existence in every such graph of an ordering of the vertices with a special property. More generally we prove, using a variant of lexicographic breadth-first search, that in every graph that contains no bull and no hole of length at least five there is a vertex that is not the middle of a chordless path on five vertices. This latter fact also generalizes known results about chordal bipartite graphs, totally balanced matrices, and strongly chordal graphs.