Characterization and recognition of P₄-sparse graphs partitionable into k independent sets and cliques

DOI10.1016/J.DAM.2010.10.019zbMATH Open1210.05106OpenAlexW2126636456MaRDI QIDQ629355FDOQ629355

Authors: Raquel S. F. Bravo, Sulamita Klein, Loana T. Nogueira, Fábio Protti 

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

Recommendations

• Partitioning extended \(P_4\)-laden graphs into cliques and stable sets
• On variations of \(P_{4}\)-sparse graphs
• Partitioning sparse graphs into an independent set and a graph with bounded size components
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• On semi-\(P_ 4\)-sparse graphs
• On the recognition of \(P_4\)-indifferent graphs
• Independent sets in \(\{\text{claw}, K_4 \}\)-free 4-regular graphs
• Minimal separators in \(P_4\)-sparse graphs
• On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
• A Fully Dynamic Algorithm for the Recognition of P 4-Sparse Graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Complement reducible graphs
• Modular decomposition and transitive orientation
• A tree representation for \(P_ 4\)-sparse graphs
• Partitioning chordal graphs into independent sets and cliques
• Partitions of graphs into one or two independent sets and cliques
• Complexity of graph partition problems
• A Linear Recognition Algorithm for Cographs
• List Partitions
• The complexity of some problems related to GRAPH 3-COLORABILITY
• A simple linear time LexBFS cograph recognition algorithm.
• Matrix partitions of perfect graphs
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• Partitioning cographs into cliques and stable sets
• Generalized colouring (matrix partitions) of cographs
• Title not available (Why is that?)
• Linear time optimization algorithms for \(P_ 4\)-sparse graphs

Cited In (8)

• On variations of \(P_{4}\)-sparse graphs
• Fixed-parameter algorithms for the cocoloring problem
• Edge clique partition in \((k,\ell)\)-graphs
• Partitioning a graph into disjoint cliques and a triangle-free graph
• Partitioning extended \(P_4\)-laden graphs into cliques and stable sets
• 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
• Characterizing –partitionable Cographs

This page was built for publication: Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q629355)