Classes of perfect graphs
From MaRDI portal
Publication:2433714
DOI10.1016/j.disc.2006.05.021zbMath1104.05029OpenAlexW2028360319MaRDI QIDQ2433714
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
Related Items (15)
Forbidden induced pairs for perfectness and \(\omega\)-colourability of graphs ⋮ Structural properties of Toeplitz graphs ⋮ New characterizations of Gallai's \(i\)-triangulated graphs ⋮ Structural properties of super strongly perfect graphs ⋮ On some graph classes related to perfect graphs: a survey ⋮ Structure of super strongly perfect graphs ⋮ Cograph generation with linear delay ⋮ Unconditional reflexive polytopes ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ On cover-structure graphs ⋮ An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs ⋮ Strong cliques in diamond-free graphs ⋮ Online coloring a token graph ⋮ Unnamed Item ⋮ OPEN PACKING NUMBER FOR SOME CLASSES OF PERFECT 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
- 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
- P4-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
- A good characterization of cograph contractions
- 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
- Wing-triangulated graphs are perfect
- Transitiv orientierbare Graphen
- The Strong Perfect Graph Conjecture for Planar Graphs
This page was built for publication: Classes of perfect graphs
