Bounding the Clique‐Width of H‐Free Chordal Graphs. Issue 1 (10th February 2017)

• Record Type: Journal Article
• Authors: Brandstädt, Andreas; Dabrowski, Konrad K.; Huang, Shenwei; Paulusma, Daniël
• Is Part Of: Journal of graph theory. Volume 86:Issue 1(2017)
• Page Start: 42
• Page End: 77
• Publication Date: 2017-02-10
• Subjects: clique‐width -- chordal graph -- forbidden induced subgraph -- hereditary graph class; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22111
• Languages: English
• ISSNs: 0364-9024

Abstract

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 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.