A description of claw-free perfect graphs

DOI10.1006/jctb.1998.1872zbMath0933.05062MaRDI 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 characterization; matching; augmentation; claw-free graph; line graph; polynomial algorithm; perfect graphs; connected graph; Berge graphs; elementary graph; bipartite multigraph; wonders

Mathematics Subject Classification ID

05C75: Structural characterization of families of graphs

05C85: Graph algorithms (graph-theoretic aspects)

05C17: Perfect graphs

Related Items

Even pairs in claw-free perfect graphs, Graphs without odd holes, parachutes or proper wheels: A generalization of Meyniel graphs and of line graphs of bipartite graphs, On the choice number of claw-free perfect graphs, A transformation which preserves the clique number, Classes of perfect graphs, Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs, A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs, Bounding χ in terms of ω and Δ for quasi-line 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