Recognizing well covered graphs of families with special \(P _{4}\)-components

DOI10.1007/s00373-011-1123-1zbMath1267.05207MaRDI QIDQ2376085

Sulamita Klein, Aurora Morgana, Célia Picinin de Mello

Publication date: 26 June 2013

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-011-1123-1

zbMATH Keywords

modular decomposition; primeval decomposition; well covered graphs; graphs with few \(P _{4}\)'s

Mathematics Subject Classification ID

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

Related Items

Recognizing well-dominated graphs is coNP-complete, Graphs with few \(P_4\)'s under the convexity of paths of order three, On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity, On the probe problem for \((r,\ell )\)-well-coveredness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the well-coveredness of Cartesian products of graphs
• Complement reducible graphs
• The splittance of a graph
• On a unique tree representation for \(P_ 4\)-extendible graphs
• A tree representation for \(P_ 4\)-sparse graphs
• A characterization of well covered graphs of girth 5 or greater
• Modular decomposition and transitive orientation
• Well-covered graphs and extendability
• The structure of well-covered graphs and the complexity of their recognition problems
• On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
• Well-covered graphs and factors
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• A New Class of Brittle Graphs
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Complexity results for well‐covered graphs
• WELL-COVERED GRAPHS: A SURVEY
• Subdivisions, parity and well-covered graphs
• P-Components and the Homogeneous Decomposition of Graphs
• Recognizing Greedy Structures
• Well covered simplicial, chordal, and circular arc graphs
• Some covering concepts in graphs