Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques
From MaRDI portal
Publication:629355
DOI10.1016/j.dam.2010.10.019zbMath1210.05106OpenAlexW2126636456MaRDI QIDQ629355
Sulamita Klein, Loana Tito Nogueira, Fábio Protti, Raquel S. F. Bravo
Publication date: 9 March 2011
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2010.10.019
Related Items (6)
Structural characterization and decomposition for cographs-(2, 1) and (1, 2): a natural generalization of threshold graphs ⋮ The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy ⋮ Fixed-parameter algorithms for the cocoloring problem ⋮ Partitioning extended \(P_4\)-laden graphs into cliques and stable sets ⋮ Edge clique partition in \((k,\ell)\)-graphs ⋮ Partitioning a graph into disjoint cliques and a triangle-free graph
Cites Work
- Unnamed Item
- Unnamed Item
- Complement reducible graphs
- A tree representation for \(P_ 4\)-sparse graphs
- The complexity of some problems related to GRAPH 3-COLORABILITY
- Modular decomposition and transitive orientation
- Partitioning chordal graphs into independent sets and cliques
- Linear time optimization algorithms for \(P_ 4\)-sparse graphs
- Partitions of graphs into one or two independent sets and cliques
- Matrix partitions of perfect graphs
- Partitioning cographs into cliques and stable sets
- Complexity of graph partition problems
- P4-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
- A Linear Recognition Algorithm for Cographs
- Recognizing $P_4 $-Sparse Graphs in Linear Time
- List Partitions
- Graph-Theoretic Concepts in Computer Science
This page was built for publication: Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques
