Brandstädt, A. and Dabrowski, K.K. and Huang, S. and Paulusma, D. (2015) 'Bounding the clique-width of H-free chordal graphs.', in Mathematical foundations of computer science 2015 : 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, proceedings, part II. Berlin: Springer, pp. 139-150. Lecture notes in computer science. (9235).
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.
|Item Type:||Book chapter|
|Full text:||(AM) Accepted Manuscript|
Download PDF (423Kb)
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-662-48054-0_12|
|Publisher statement:||The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-48054-0_12|
|Date accepted:||No date available|
|Date deposited:||19 August 2015|
|Date of first online publication:||August 2015|
|Date first made open access:||11 August 2016|
Save or Share this output
|Look up in GoogleScholar|