A description of claw-free perfect graphs

DOI10.1006/JCTB.1998.1872MaRDI QIDQ1306428zbMATH OpenOpenAlexFDO

Authors Frédéric Maffray, Bruce 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

matchingconnected graphline graphclaw-free graphpolynomial algorithmperfect graphsstructural characterizationaugmentationBerge graphselementary graphbipartite multigraphwonders

Mathematics Subject Classification ID

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

Recommendations

• The structure of claw-free perfect graphs
• Which claw-free graphs are perfectly orderable?
• Claw-free graphs. IV: Decomposition theorem
• The structure of claw-free graphs
• Two classes of perfect graphs

Cites work

• scientific article; zbMATH DE number 3884202 (Why is no real title available?)
• scientific article; zbMATH DE number 3902654 (Why is no real title available?)
• scientific article; zbMATH DE number 3893237 (Why is no real title available?)
• A characterization of perfect graphs
• A partial characterization of clique graphs
• Algorithms on clique separable graphs
• An algorithm for finding clique cut-sets
• Bull-free Berge graphs are perfect
• Compositions for perfect graphs
• Decomposition by clique separators
• Recognizing claw-free perfect graphs
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs

Cited in

(28)

• A transformation which preserves the clique number
• A survey of the studies on Gallai and anti-Gallai graphs
• Edge-intersection graphs of boundary-generated paths in a grid
• Even pairs in claw-free perfect graphs
• On claw-free t-perfect graphs
• A characterization of claw-free \(b\)-perfect graphs
• Strongly perfect claw‐free graphs—A short proof
• Claw-free strictly Deza graphs
• On the choosability of claw-free perfect graphs
• The structure of 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 box-perfect graphs
• A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
• Star coloring of certain graph classes
• On the choice number of claw-free perfect graphs
• Forests and trees among Gallai graphs
• Total coloring of quasi-line graphs and inflated graphs
• Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
• Classes of perfect graphs
• Excluding hooks and their complements
• Perfect graphs with polynomially computable kernels
• Minimum weighted clique cover on claw‐free perfect graphs
• Bounding χ in terms of ω and Δ for quasi-line graphs
• Claw-free graphs, skeletal graphs, and a stronger conjecture on \(\omega\), \(\Delta\), and \(\chi\)
• Counting weighted independent sets beyond the permanent
• Square-Free Graphs with No Six-Vertex Induced Path
• More relations between \(\lambda \)-labeling and Hamiltonian paths with emphasis on line graph of bipartite multigraphs
• Finding induced paths of given parity in claw-free graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1306428)