Bounding the Clique-Width of H-free Chordal Graphs

Brandstädt, A.; Dabrowski, K.K.; Huang, S.; Paulusma, D.

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.

Citation

Brandstädt, A., Dabrowski, K., Huang, S., & Paulusma, D. (2015, August). Bounding the Clique-Width of H-free Chordal Graphs. Presented at 40th International Symposium, MFCS 2015, Milan, Italy

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 40th International Symposium, MFCS 2015
• Publication Date: Aug 11, 2015
• Deposit Date: Aug 12, 2015
• Publicly Available Date: Aug 11, 2016
• Print ISSN: 0302-9743
• Pages: 139-150
• Series Title: Lecture notes in computer science
• Series Number: 9235
• Series ISSN: 0302-9743
• Book Title: Mathematical foundations of computer science 2015 : 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, proceedings, part II.
• ISBN: 9783662480533
• DOI: https://doi.org/10.1007/978-3-662-48054-0_12
• Public URL: https://durham-repository.worktribe.com/output/1152234
• Additional Information: Conference dates: August 24-28, 2015,