Publication detailsBrandstädt, A., Dabrowski, K.K., Huang, S. & Paulusma, D. (2017). Bounding the Clique-Width of H-free Chordal Graphs. Journal of Graph Theory 86(1): 42-77.
- Publication type: Journal Article
- ISSN/ISBN: 0364-9024, 1097-0118
- DOI: 10.1002/jgt.22111
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
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 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 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 inline image-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.