Bounding the Clique-Width of H-free Chordal Graphs

Abstract

A graph is H-free if it has no induced subgraph isomorphic to H. Brandstädt, Engelfriet, Le and Lozin proved that the class of chordal graphs with independence number at most 3 has unbounded clique-width. Brandstädt, Le and Mosca erroneously claimed that the gem and the co-gem are the only two 1-vertex P4-extensions H for which the class of H-free chordal graphs has bounded clique-width. In fact we prove that bull-free chordal and co-chair-free chordal graphs have clique-width at most 3 and 4, respectively. In particular, we prove that the clique-width is: (i) bounded for four classes of H-free chordal graphs; (ii) unbounded for three subclasses of split graphs. Our main result, obtained by combining new and known results, provides a classification of all but two stubborn cases, that is, with two potential exceptions we determine all graphs H for which the class of H-free chordal graphs has bounded clique-width. We illustrate the usefulness of this classification for classifying other types of graph classes by proving that the class of (2P1+P3,K4)-free graphs has bounded clique-width via a reduction to K4-free chordal graphs. Finally, we give a complete classification of the (un)boundedness of clique-width of H-free weakly chordal graphs.