On some graph classes related to perfect graphs: a survey
DOI10.1016/j.dam.2019.05.019zbMath1440.05099OpenAlexW2974092235WikidataQ127228325 ScholiaQ127228325MaRDI QIDQ2184662
Guillermo Durán, Annegret K. Wagler, Martín D. Safe, Flavia Bonomo-Braberman
Publication date: 29 May 2020
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://hal.uca.fr/hal-03142102/file/BDSW_survey_perfect_graphs_HAL.pdf
perfect graphsbalanced graphsclique-perfect graphscoordinated graphsneighborhood-perfect graphs\(K\)-perfect graphs
Hypergraphs (05C65) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17)
Related Items
Cites Work
- Maximum \(h\)-colourable subgraph problem in balanced graphs
- Clique-perfectness of claw-free planar graphs
- Topics on perfect graphs
- The strong perfect graph theorem
- Kernels in perfect line-graphs
- Algorithms for finding clique-transversals of graphs
- Partial characterizations of coordinated graphs: Line graphs and complements of forests
- Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs
- The strong perfect graph conjecture: 40 years of attempts, and its resolution
- Characterizations of strongly chordal graphs
- Neighborhood perfect graphs
- Distance-hereditary graphs
- Recognizing claw-free perfect graphs
- Strong tree-cographs are Birkhoff graphs
- Complement reducible graphs
- Covering the cliques of a graph with vertices
- Neighbourhood-perfect line graphs
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- On certain polytopes associated with graphs
- Progress on perfect graphs
- Balanced \(0,\pm 1\) matrices. II: Recognition algorithm
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- On clique-transversals and clique-independent sets
- Triangle-free four-chromatic graphs
- Triangle-free graphs with large chromatic numbers
- Algorithmic aspects of clique-transversal and clique-independent sets
- Classes of perfect graphs
- Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
- Distance-hereditary graphs are clique-perfect
- Recognizing Berge graphs
- Algorithms for clique-independent sets on subclasses of circular-arc graphs
- Normal hypergraphs and the perfect graph conjecture
- A polynomial recognition algorithm for balanced matrices
- Recognizing balanceable matrices
- On balanced graphs
- A decomposition theorem for partially ordered sets
- Clique-perfectness and balancedness of some graph classes
- Clique r-Domination and Clique r-Packing Problems on Dually Chordal Graphs
- Minimally Unbalanced Diamond-Free Graphs and Dyck-Paths
- Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
- Algorithms on circular-arc graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- A New Algorithm for Generating All the Maximal Independent Sets
- Graph Classes: A Survey
- Minimal non-neighborhood-perfect graphs
- Algorithmic Aspects of Neighborhood Numbers
- Berge trigraphs
- Transitiv orientierbare Graphen
- Balanced matrices
- Sur le coloriage des graphs
- Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
- Clique-perfectness of complements of line 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
- Unnamed Item
