Bounding the Clique‐Width of H ‐Free Chordal Graphs

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 co‐gem are the only two 1‐vertex P 4 ‐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 find four new classes of H ‐free chordal graphs of bounded clique‐width. 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 ( 2 P 1 + P 3 , K 4 ) ‐free graphs has bounded clique‐width via a reduction to K 4 ‐free chordal graphs. Finally, we give a complete classification of the (un)boundedness of clique‐width of H ‐free weakly chordal graphs.