Critical perfect graphs and perfect 3-chromatic graphs

DOI10.1016/0095-8956(77)90064-8zbMath0376.05047OpenAlexW2075256009MaRDI QIDQ1245851

Alan C. Tucker

Publication date: 1977

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(77)90064-8

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph theory (05C99)

Related Items (33)

Near-perfect matrices ⋮ New classes of Berge perfect graphs ⋮ Claw‐free circular‐perfect graphs ⋮ Alternating orientation and alternating colouration of perfect graphs ⋮ A reduction procedure for coloring perfect \(K_ 4\)-free graphs ⋮ On transversals in minimal imperfect graphs ⋮ Binary integer programs with two variables per inequality ⋮ Two classes of perfect graphs ⋮ The strong perfect graph conjecture for pan-free graphs ⋮ Chair-free Berge graphs are perfect ⋮ Star-cutsets and perfect graphs ⋮ On perfect graphs and polyhedra with (0, 1)-valued extreme points ⋮ Gallai graphs and anti-Gallai graphs ⋮ Some properties of minimal imperfect graphs ⋮ Graphical properties related to minimal imperfection ⋮ $t$-Perfection in $P_5$-Free Graphs ⋮ Circular-imperfection of triangle-free graphs ⋮ Three-colourable perfect graphs without even pairs ⋮ The strong perfect graph conjecture for toroidal graphs ⋮ A classification of certain graphs with minimal imperfection properties ⋮ On the strong perfect graph conjecture and critical graphs ⋮ Square-free perfect graphs. ⋮ On stable set polyhedra for K//(1,3)free graphs ⋮ Forced color classes, intersection graphs and the strong perfect graph conjecture ⋮ Bounded vertex colorings of graphs ⋮ \(K_{4}\)-free graphs with no odd holes ⋮ Combinatorial designs related to the strong perfect graph conjecture ⋮ Unnamed Item ⋮ An algorithm for colouring perfect planar graphs ⋮ Partitionable graphs, circle graphs, and the Berge strong perfect graph conjecture ⋮ The edge intersection graphs of paths in a tree ⋮ Quasi-star-cutsets and some consequences ⋮ Decomposition of perfect graphs

Cites Work

• Unnamed Item
• Unnamed Item
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
• Anti-blocking polyhedra
• A characterization of perfect graphs
• Normal hypergraphs and the perfect graph conjecture
• Coloring a Family of Circular Arcs
• Perfect zero–one matrices
• Remarks on a Problem of Moser
• The Strong Perfect Graph Conjecture for Planar Graphs
• Blocking and anti-blocking pairs of polyhedra
• On the strong perfect graph conjecture

This page was built for publication: Critical perfect graphs and perfect 3-chromatic graphs