A description of claw-free perfect graphs

DOI10.1006/jctb.1998.1872zbMath0933.05062OpenAlexW2076296189MaRDI QIDQ1306428

Frédéric Maffray, Bruce A. Reed

Publication date: 4 April 2000

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

Full work available at URL: https://semanticscholar.org/paper/7017526f7f632c773511187ebd996fa5515a2598

zbMATH Keywords

structural characterizationmatchingaugmentationclaw-free graphline graphpolynomial algorithmperfect graphsconnected graphBerge graphselementary graphbipartite multigraphwonders

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17)

Related Items (27)

Claw-free strictly Deza graphs ⋮ Excluding hooks and their complements ⋮ Even pairs in claw-free perfect graphs ⋮ On box-perfect graphs ⋮ Minimum weighted clique cover on claw‐free perfect graphs ⋮ Strongly perfect claw‐free graphs—A short proof ⋮ Edge-intersection graphs of boundary-generated paths in a grid ⋮ Graphs without odd holes, parachutes or proper wheels: A generalization of Meyniel graphs and of line graphs of bipartite graphs ⋮ Finding induced paths of given parity in claw-free graphs ⋮ Classes of perfect graphs ⋮ Star coloring of certain graph classes ⋮ On the choice number of claw-free perfect graphs ⋮ Forests and trees among Gallai graphs ⋮ A characterization of claw-free \(b\)-perfect graphs ⋮ Unnamed Item ⋮ On the choosability of claw-free perfect graphs ⋮ The Structure of Claw‐Free Perfect Graphs ⋮ Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs ⋮ Bounding χ in terms of ω and Δ for quasi-line graphs ⋮ Perfect graphs with polynomially computable kernels ⋮ Claw‐Free Graphs, Skeletal Graphs, and a Stronger Conjecture on ω, Δ, and χ ⋮ Square-Free Graphs with No Six-Vertex Induced Path ⋮ Counting Weighted Independent Sets beyond the Permanent ⋮ A transformation which preserves the clique number ⋮ A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs ⋮ Total coloring of quasi-line graphs and inflated graphs ⋮ A survey of the studies on Gallai and anti-Gallai graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decomposition by clique separators
• Bull-free Berge graphs are perfect
• Recognizing claw-free perfect graphs
• 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
• Compositions for perfect graphs
• A characterization of perfect graphs
• A partial characterization of clique graphs

This page was built for publication: A description of claw-free perfect graphs