ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P4'S
From MaRDI portal
Publication:5249008
DOI10.1142/S0129054199000241zbMath1320.05096MaRDI QIDQ5249008
Johann A. Makowsky, Udi Rotics
Publication date: 29 April 2015
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (44)
Polynomial algorithms for protein similarity search for restricted mRNA structures ⋮ On spectra of sentences of monadic second order logic with counting ⋮ Colouring diamond-free graphs ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ Colouring square-free graphs without long induced paths. ⋮ 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 ⋮ Clique‐width: Harnessing the power of atoms ⋮ Graph classes with and without powers of bounded clique-width ⋮ Independent domination in finitely defined classes of graphs ⋮ Bounding clique-width via perfect graphs ⋮ Tree-width and the monadic quantifier hierarchy. ⋮ Graphs of separability at most 2 ⋮ Clique-Width for Graph Classes Closed under Complementation ⋮ On variations of \(P_{4}\)-sparse graphs ⋮ On the structure of (pan, even hole)‐free graphs ⋮ Classifying the clique-width of \(H\)-free bipartite graphs ⋮ On the structure and stability number of \(P_{5}\)- and co-chair-free graphs ⋮ THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES ⋮ Bounding the clique-width of \(H\)-free split graphs ⋮ Minimal classes of graphs of unbounded clique-width ⋮ Graphs of Separability at Most Two: Structural Characterizations and Their Consequences ⋮ Polynomial cases for the vertex coloring problem ⋮ Counting truth assignments of formulas of bounded tree-width or clique-width ⋮ On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic ⋮ Recent developments on graphs of bounded clique-width ⋮ Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width ⋮ Split permutation graphs ⋮ On the complexity of the dominating induced matching problem in hereditary classes of graphs ⋮ Bounding Clique-Width via Perfect Graphs ⋮ Bounding the clique-width of \(H\)-free split graphs ⋮ Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs ⋮ Unnamed Item ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Square-Free Graphs with No Six-Vertex Induced Path ⋮ Chordal bipartite graphs of bounded tree- and clique-width ⋮ Dominating Induced Matchings ⋮ Colouring square-free graphs without long induced paths ⋮ ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES ⋮ Optimal centrality computations within bounded clique-width graphs ⋮ Maximum matching in almost linear time on graphs of 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
Cites Work
- A linear-time recognition algorithm for \(P_{4}\)-reducible graphs
- Complement reducible graphs
- \(k\)-NLC graphs and polynomial algorithms
- On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
- On the structure of graphs with few \(P_4\)s
- P4-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
- A Fast Algorithm for the Decomposition of Graphs and Posets
- Recognizing $P_4 $-Sparse Graphs in Linear Time
This page was built for publication: ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P4'S
