Classes of perfect graphs

DOI10.1016/j.disc.2006.05.021zbMath1104.05029MaRDI QIDQ2433714

Stefan Hougardy

Publication date: 30 October 2006

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

Full work available at URL: https://doi.org/10.1016/j.disc.2006.05.021

zbMATH Keywords

survey; graph classes; algorithmic properties

Mathematics Subject Classification ID

05C17: Perfect graphs

Related Items

On cover-structure graphs

Cites Work

• Blocking and anti-blocking pairs of polyhedra
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• A Characterization of Comparability Graphs and of Interval Graphs
• Partially Ordered Sets
• An \(O(n^2)\) algorithm to color Meyniel graphs
• Finding houses and holes in graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recognizing \(i\)-triangulated graphs in \(O(mn)\) time
• Skeletal graphs - a new class of perfect graphs
• Preperfect graphs
• The validity of the strong perfect-graph conjecture for \((K_4-e)\)-free graphs
• On rigid circuit graphs
• Weakly triangulated graphs
• Perfectly contractile graphs
• The strong perfect graph theorem
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• On the complexity of recognizing perfectly orderable graphs
• Decomposition by clique separators
• Coloring perfect \((K_ 4\)-e)-free graphs
• Matching theory
• Alternating orientation and alternating colouration of perfect graphs
• Bull-free Berge graphs are perfect
• Slender graphs
• Murky graphs
• A new property of critical imperfect graphs and some consequences
• Locally perfect graphs
• Paw-free graphs
• A fast algorithm for coloring Meyniel graphs
• Two classes of perfect graphs
• All variations on perfectly orderable graphs
• Recognizing claw-free perfect graphs
• Star-cutsets and perfect graphs
• Slim graphs
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Algorithms for minimum covering by cliques and maximum clique in claw- free perfect graphs
• The strong perfect graph conjecture for toroidal graphs
• The splittance of a graph
• The ellipsoid method and its consequences in combinatorial optimization
• The strong perfect graph conjecture holds for diamonded odd cycle-free graphs
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Algorithms on clique separable graphs
• Trivially perfect graphs
• On the perfect graph conjecture
• On the extension of bipartite to parity graphs
• A description of claw-free perfect graphs
• Perfect graphs with no \(P_ 5\) and no \(K_ 5\)
• Slightly triangulated graphs are perfect
• Coloring perfect degenerate graphs
• Chair-free Berge graphs are perfect
• Square-free perfect graphs.
• On \(P_4\)-transversals of perfect graphs
• A linear algorithm to color \(i\)-triangulated graphs
• On the \(P_ 4\)-structure of perfect graphs. IV: Partner graphs
• Recognizing brittle graphs: Remarks on a paper of Hoàng and Khouzam
• An algorithm for colouring perfect planar graphs
• On the semi-perfect elimination
• Independent sets of maximum weight in (\(p,q\))-colorable graphs.
• Algorithms for weakly triangulated graphs
• Split-neighbourhood graphs and the strong perfect graph conjecture
• Recognizing bull-free perfect graphs
• On the \(P_ 4\)-structure of perfect graphs. V: Overlap graphs
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Recognizing Berge graphs
• On a property of the class of n-colorable graphs
• A decomposition theorem for partially ordered sets
• Recognizing Dart-Free Perfect Graphs
• Representation of a finite graph by a set of intervals on the real line
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• A New Class of Brittle Graphs
• A Linear Recognition Algorithm for Cographs
• On brittle graphs
• How To Color Claw-Free Perfect Graphs
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• Algorithmic Aspects of Vertex Elimination on Graphs
• Line perfect graphs
• Graph Classes: A Survey
• Independent Sets in Asteroidal Triple-Free Graphs
• Asteroidal Triple-Free Graphs
• Optimizing Bull-Free Perfect Graphs
• Precoloring Extension III: Classes of Perfect Graphs
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Recognizing Perfect 2-Split Graphs
• HOLES AND DOMINOES IN MEYNIEL GRAPHS
• Transitiv orientierbare Graphen
• The Strong Perfect Graph Conjecture for Planar Graphs