Graph transformations preserving the stability number

DOI10.1016/j.dam.2011.08.023zbMath1254.05166MaRDI QIDQ5916099

Dominique de Werra, Benjamin Lévêque

Publication date: 22 November 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.08.023

zbMATH Keywords

stability number; perfect graph; even pair; graph transformations; edge deletions; twin deletions

Mathematics Subject Classification ID

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

05C17: Perfect graphs

05C76: Graph operations (line graphs, products, etc.)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• Perfectly contractile graphs
• The strong perfect graph theorem
• A magnetic procedure for the stability number
• Even pairs in Berge graphs
• Coloring Artemis graphs
• A new property of critical imperfect graphs and some consequences
• Complement reducible graphs
• The ellipsoid method and its consequences in combinatorial optimization
• On the use of Boolean methods for the computation of the stability number
• Struction revisited
• Dirac-type characterizations of graphs without long chordless cycles
• A class of perfectly contractile graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Stability in circular arc graphs
• Transformations which Preserve Perfectness and H-Perfectness of Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Local transformations of graphs preserving independence number
• Graph transformations preserving the stability number