Bounded Clique-Width of (S_1,2,2,Triangle)-Free Graphs

2016/08/05 by Brandstadt, Andreas, Mahfud, Suhail, Mosca, Raffaele
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1608.01820

Abstract

If a graph has no induced subgraph isomorphic to H₁ or H₂ then it is said to be (H₁,H₂)-free. Dabrowski and Paulusma found 13 open cases for the question whether the clique-width of (H₁,H₂)-free graphs is bounded. One of them is the class of (S_1,2,2,triangle)-free graphs. In this paper we show that these graphs have bounded clique-width. Thus, also (P₁+2P₂,triangle)-free graphs have bounded clique-width which solves another open problem of Dabrowski and Paulusma. Meanwhile we were informed by Paulusma that in December 2015, Dabrowski, Dross and Paulusma showed that (S_1,2,2,triangle)-free graphs (and some other graph classes) have bounded clique-width.

Related

• Bounding Clique-Width via Perfect Graphs
• Bounding the Clique-Width of H-free Split Graphs
• Clique-width of Graph Classes Defined by Two Forbidden Induced Subgraphs
• Bounding the Clique-Width of H-free Chordal Graphs
• Clique-Width: Harnessing the Power of Atoms