Bounding the Clique-Width of $H$-free Split Graphs
Preprint
Abstract
A graph is $H$-free if it has no induced subgraph isomorphic to $H$. We continue a study into the boundedness of clique-width of subclasses of perfect graphs. We identify five new classes of $H$-free split graphs whose clique-width is bounded. 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 split graphs has bounded clique-width.
Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Classifying the clique-width of -free bipartite graphsDiscrete Applied Mathematics, 2016
- Graph classes with and without powers of bounded clique-widthDiscrete Applied Mathematics, 2016
- Characterising the linear clique-width of a class of graphs by forbidden induced subgraphsDiscrete Applied Mathematics, 2012
- Colouring vertices of triangle-free graphs without forestsDiscrete Mathematics, 2012
- Polynomial-time recognition of clique-width ≤3 graphsDiscrete Applied Mathematics, 2012
- Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced SubgraphsLecture Notes in Computer Science, 2012
- Recent developments on graphs of bounded clique-widthDiscrete Applied Mathematics, 2009
- Clique-Width for 4-Vertex Forbidden SubgraphsTheory of Computing Systems, 2006
- Chordal co-gem-free and (P5,gem)-free graphs have bounded clique-widthDiscrete Applied Mathematics, 2005
- On the structure of (,gem)-free graphsDiscrete Applied Mathematics, 2005