Classes of perfect graphs
From MaRDI portal
Publication:2433714
DOI10.1016/J.DISC.2006.05.021zbMATH Open1104.05029OpenAlexW2028360319MaRDI QIDQ2433714FDOQ2433714
Authors: 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
Recommendations
Cites Work
- Title not available (Why is that?)
- A linear algorithm to color \(i\)-triangulated graphs
- On the \(P_ 4\)-structure of perfect graphs. IV: Partner graphs
- Recognizing Perfect 2-Split Graphs
- A good characterization of cograph contractions
- Wing-triangulated graphs are perfect
- Title not available (Why is that?)
- Matching theory
- Title not available (Why is that?)
- Graph Classes: A Survey
- Decomposition by clique separators
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- The ellipsoid method and its consequences in combinatorial optimization
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- Title not available (Why is that?)
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- On rigid circuit graphs
- The strong perfect graph theorem
- Trivially perfect graphs
- Recognizing Berge graphs
- Representation of a finite graph by a set of intervals on the real line
- Transitiv orientierbare Graphen
- A Characterization of Comparability Graphs and of Interval Graphs
- On maximal independent sets of vertices in claw-free graphs
- Asteroidal Triple-Free Graphs
- Blocking and anti-blocking pairs of polyhedra
- Partially Ordered Sets
- Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
- The splittance of a graph
- Title not available (Why is that?)
- A New Class of Brittle Graphs
- Title not available (Why is that?)
- Algorithmic Aspects of Vertex Elimination on Graphs
- Weakly triangulated graphs
- Coloring perfect \((K_ 4\)-e)-free graphs
- Paw-free graphs
- Recognizing bull-free perfect graphs
- A decomposition theorem for partially ordered sets
- Recognizing \(i\)-triangulated graphs in \(O(mn)\) time
- Title not available (Why is that?)
- A Linear Recognition Algorithm for Cographs
- Title not available (Why is that?)
- Algorithms on clique separable graphs
- Square-free perfect graphs.
- Algorithms for weakly triangulated graphs
- Independent Sets in Asteroidal Triple-Free Graphs
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- Perfectly contractile graphs
- Slender graphs
- All variations on perfectly orderable graphs
- Star-cutsets and perfect graphs
- Slim graphs
- Title not available (Why is that?)
- Optimizing Bull-Free Perfect Graphs
- On the complexity of recognizing perfectly orderable graphs
- On the semi-perfect elimination
- P4-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
- On a property of the class of n-colorable graphs
- Precoloring Extension III: Classes of Perfect Graphs
- Bull-free Berge graphs are perfect
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A fast algorithm for coloring Meyniel graphs
- On the perfect graph conjecture
- Title not available (Why is that?)
- Line perfect graphs
- Holes and dominoes in Meyniel graphs
- An \(O(n^2)\) algorithm to color Meyniel graphs
- A description of claw-free perfect graphs
- Recognizing $P_4 $-Sparse Graphs in Linear Time
- Recognizing claw-free perfect graphs
- On the extension of bipartite to parity graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Recognizing Dart-Free Perfect Graphs
- The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
- On \(P_4\)-transversals of perfect graphs
- Independent sets of maximum weight in (\(p,q\))-colorable graphs.
- A new property of critical imperfect graphs and some consequences
- Skeletal graphs - a new class of perfect graphs
- The Strong Perfect Graph Conjecture for Planar Graphs
- Origins and genesis
- Alternating orientation and alternating colouration of perfect graphs
- On brittle graphs
- Preperfect graphs
- The validity of the strong perfect-graph conjecture for \((K_4-e)\)-free graphs
- Finding houses and holes in graphs
- The strong perfect graph conjecture for toroidal graphs
- Title not available (Why is that?)
- Two classes of perfect graphs
- Chair-free Berge graphs are perfect
- Split-neighbourhood graphs and the strong perfect graph conjecture
- Perfect graphs with no \(P_ 5\) and no \(K_ 5\)
- Algorithms for minimum covering by cliques and maximum clique in claw- free perfect graphs
- Coloring perfect degenerate graphs
- An algorithm for colouring perfect planar graphs
- Murky graphs
- Locally perfect graphs
- How To Color Claw-Free Perfect Graphs
- Title not available (Why is that?)
- The strong perfect graph conjecture holds for diamonded odd cycle-free graphs
- On the \(P_ 4\)-structure of perfect graphs. V: Overlap graphs
- Slightly triangulated graphs are perfect
- Recognizing brittle graphs: Remarks on a paper of Hoàng and Khouzam
Cited In (25)
- New classes of perfect graphs
- On cover-structure graphs
- Strong cliques in diamond-free graphs
- The strong perfect graph theorem
- Forbidden induced pairs for perfectness and \(\omega\)-colourability of graphs
- Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
- Two classes of perfect graphs
- An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs
- How the proof of the strong perfect graph conjecture was found
- On some graph classes related to perfect graphs: a survey
- On edge perfectness and classes of bipartite graphs
- Chromatic and clique numbers of a class of perfect graphs
- Structural properties of Toeplitz graphs
- Unconditional reflexive polytopes
- Open packing number for some classes of perfect graphs
- Title not available (Why is that?)
- The strong perfect graph conjecture: 40 years of attempts, and its resolution
- New characterizations of Gallai's \(i\)-triangulated graphs
- On a Class of P 5 -Free Graphs
- Cograph generation with linear delay
- Online coloring a token graph
- Structural properties of super strongly perfect graphs
- Title not available (Why is that?)
- Structure of super strongly perfect graphs
- Classes of graphs which approximate the complete Euclidean graph
This page was built for publication: Classes of perfect graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2433714)
