Recognizing claw-free perfect graphs

DOI10.1016/0095-8956(88)90085-8zbMath0669.05054OpenAlexW2095243185MaRDI QIDQ1118619

Vašek Chvátal, Najiba Sbihi

Publication date: 1988

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(88)90085-8

zbMATH Keywords

claw-free graphchromatic numberperfect graphs

Mathematics Subject Classification ID

Trees (05C05) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Related Items (49)

Forbidden induced subgraphs for perfectness of claw-free graphs of independence number at least 4 ⋮ On coloring a class of claw-free graphs. ⋮ On dart-free perfectly contractile graphs ⋮ Alternating orientation and alternating colouration of perfect graphs ⋮ On the chromatic number of \(2 K_2\)-free graphs ⋮ Claw-free graphs---a survey ⋮ In praise of Claude Berge ⋮ Path parity and perfection ⋮ Choice number of 3-colorable elementary graphs ⋮ Paw-free graphs ⋮ On the structure of graphs without claw, \(4K_1\) and co-R ⋮ On a conjecture about uniquely colorable perfect graphs ⋮ Excluding hooks and their complements ⋮ Gallai graphs and anti-Gallai graphs ⋮ Even pairs in claw-free perfect graphs ⋮ Intersection graphs of proper subtrees of unicyclic graphs ⋮ On some graph classes related to perfect graphs: a survey ⋮ A coloring algorithm for \(4 K_1\)-free line graphs ⋮ Minimum weighted clique cover on claw‐free perfect graphs ⋮ Strongly perfect claw‐free graphs—A short proof ⋮ Some properties of graphs determined by edge zeta functions ⋮ Divisibility and coloring of some \(P_5\)-free graphs ⋮ Finding induced paths of given parity in claw-free graphs ⋮ The \(k\)-in-a-path problem for claw-free graphs ⋮ Classes of perfect graphs ⋮ A Berge-keeping operation for graphs ⋮ Which claw-free graphs are strongly perfect? ⋮ On the choice number of claw-free perfect graphs ⋮ Finding a smallest odd hole in a claw-free graph using global structure ⋮ Forests and trees among Gallai graphs ⋮ EULERIAN AND HAMILTONIAN PROPERTIES OF GALLAI AND ANTI-GALLAI TOTAL GRAPHS ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ On the choosability of claw-free perfect graphs ⋮ Articulation sets in linear perfect matrices. I: Forbidden configurations and star cutsets ⋮ Which claw-free graphs are perfectly orderable? ⋮ On forbidden induced subgraphs for \(K_{1, 3}\)-free perfect graphs ⋮ The Structure of Claw‐Free Perfect Graphs ⋮ Perfect graphs with polynomially computable kernels ⋮ Claw‐Free Graphs, Skeletal Graphs, and a Stronger Conjecture on ω, Δ, and χ ⋮ Complexity of clique-coloring odd-hole-free graphs ⋮ Counting Weighted Independent Sets beyond the Permanent ⋮ The strong perfect graph conjecture: 40 years of attempts, and its resolution ⋮ On coloring a class of claw-free and hole-twin-free graphs ⋮ Minimal antichains in well-founded quasi-orders with an application to tournaments ⋮ A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs ⋮ A description of claw-free perfect graphs ⋮ Unnamed Item ⋮ Total coloring of quasi-line graphs and inflated graphs ⋮ Mortality of iterated Gallai graphs

Cites Work

• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• Weakly triangulated graphs
• Decomposition of regular matroids
• An algorithm for finding clique cut-sets
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
• Algorithms on clique separable graphs
• Transitiv orientierbare Graphen

This page was built for publication: Recognizing claw-free perfect graphs