Premium
Bounding the Clique‐Width of H ‐Free Chordal Graphs
Author(s) -
Brandstädt Andreas,
Dabrowski Konrad K.,
Huang Shenwei,
Paulusma Daniël
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22111
Subject(s) - chordal graph , combinatorics , mathematics , treewidth , split graph , clique sum , interval graph , indifference graph , discrete mathematics , bounded function , independence number , induced subgraph , pathwidth , vertex (graph theory) , graph , 1 planar graph , line graph , mathematical analysis
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.