Bounding the Clique-Width of $H$-free Chordal Graphs
Preprint
Abstract
A graph is $H$-free if it has no induced subgraph isomorphic to $H$. Brandst\"adt, Engelfriet, Le and Lozin proved that the class of chordal graphs with independence number at most 3 has unbounded clique-width. Brandst\"adt, Le and Mosca erroneously claimed that the gem and the 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 $(2P_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.
Keywords
All Related Versions
This publication has 36 references indexed in Scilit:
- Split Permutation GraphsGraphs and Combinatorics, 2013
- Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced SubgraphsLecture Notes in Computer Science, 2012
- Clique-Width for 4-Vertex Forbidden SubgraphsTheory of Computing Systems, 2006
- How to Solve NP-hard Graph Problems on Clique-Width Bounded Graphs in Polynomial Time2001
- Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-WidthTheory of Computing Systems, 2000
- Hamiltonian circuits in chordal bipartite graphsDiscrete Mathematics, 1996
- k-NLC graphs and polynomial algorithmsDiscrete Applied Mathematics, 1994
- On the vertex packing problemGraphs and Combinatorics, 1993
- On the homogeneous representation of interval graphsJournal of Graph Theory, 1991
- Paw-free graphsInformation Processing Letters, 1988