Clique-width for 4-vertex forbidden subgraphs

DOI10.1007/s00224-005-1199-1zbMath1103.68088OpenAlexW2076819776MaRDI QIDQ2432547

Joost Engelfriet, Andreas Brandstädt, Vadim V. Lozin, Hoàng-Oanh Le

Publication date: 25 October 2006

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-005-1199-1

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs ⋮ On coloring a class of claw-free graphs. ⋮ List coloring in the absence of two subgraphs ⋮ On the structure of graphs without claw, \(4K_1\) and co-R ⋮ Vertex coloring of graphs with few obstructions ⋮ Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem ⋮ Colouring diamond-free graphs ⋮ Characterizations of \((4 K_1,C_4,C_5)\)-free graphs ⋮ On quasi-planar graphs: clique-width and logical description ⋮ Bounding the Clique-Width of H-free Chordal Graphs ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ Colouring of graphs with Ramsey-type forbidden subgraphs ⋮ On the computational complexity of the bipartizing matching problem ⋮ A coloring algorithm for \(4 K_1\)-free line graphs ⋮ On the structure and clique‐width of (4K1,C4,C6,C7)‐free graphs ⋮ Clique‐width: Harnessing the power of atoms ⋮ Bichain graphs: geometric model and universal graphs ⋮ Bounding clique-width via perfect graphs ⋮ Functionality of box intersection graphs ⋮ On the clique-width of \(( 4 K_1 , C_4 , C_5 , C_7 )\)-free graphs ⋮ Clique-Width for Graph Classes Closed under Complementation ⋮ Classifying the clique-width of \(H\)-free bipartite graphs ⋮ Minimal classes of graphs of unbounded clique-width ⋮ On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size ⋮ Recent developments on graphs of bounded clique-width ⋮ A new characterization of \(P_{6}\)-free graphs ⋮ Upper domination: towards a dichotomy through boundary properties ⋮ Clique-width and well-quasi-ordering of triangle-free graph classes ⋮ On low rank-width colorings ⋮ Bounding Clique-Width via Perfect Graphs ⋮ Sandwiches missing two ingredients of order four ⋮ Bounding the clique-width of \(H\)-free split graphs ⋮ Unnamed Item ⋮ The intersection of two vertex coloring problems ⋮ On coloring a class of claw-free and hole-twin-free graphs ⋮ Optimal centrality computations within bounded clique-width graphs