Clique-Width for Graph Classes Closed under Complementation
From MaRDI portal
Publication:5112821
DOI10.1137/18M1235016zbMath1441.05167arXiv1705.07681OpenAlexW2620375528MaRDI QIDQ5112821
Matthew Johnson, Victor Zamaraev, Daniël Paulusma, Konrad K. Dabrowski, Alexandre Blanché, Vadim V. Lozin
Publication date: 9 June 2020
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1705.07681
Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy, Bounding the mim‐width of hereditary graph classes, Clique‐width: Harnessing the power of atoms, Bounding the Mim-Width of Hereditary Graph Classes.
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Colouring of graphs with Ramsey-type forbidden subgraphs
- Polynomial-time recognition of clique-width \(\leq 3\) graphs
- Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
- The behavior of clique-width under graph operations and graph transformations
- Well-quasi-ordering versus clique-width: new results on bigenic classes
- Colouring vertices of triangle-free graphs without forests
- New graph classes of bounded clique-width
- MSOL partitioning problems on graphs of bounded treewidth and clique-width
- Graph classes with and without powers of bounded clique-width
- Classifying the clique-width of \(H\)-free bipartite graphs
- Recent developments on graphs of bounded clique-width
- Characterisation of self-complementary chordal graphs
- Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
- Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
- Edge dominating set and colorings on graphs with fixed clique-width
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Graph isomorphism for \((H_1,H_2)\)-free graphs: an almost complete dichotomy
- Colouring diamond-free graphs
- Bounding clique-width via perfect graphs
- Clique-width for 4-vertex forbidden subgraphs
- Approximating clique-width and branch-width
- Selbstkomplementäre Graphen
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- Clique-Width is NP-Complete
- On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
- Hereditary graph classes: When the complexities of <scp>coloring</scp> and <scp>clique cover</scp> coincide
- ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P4'S
- Bounding the Clique‐Width of H‐Free Chordal Graphs
- Improved Bounds for the Flat Wall Theorem
- GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH
- On the Number of Self-Complementary Graphs and Digraphs
- Clique-width and well-quasi-ordering of triangle-free graph classes
- Bounding the clique-width of \(H\)-free split graphs
