On kernels in perfect graphs

DOI10.1007/BF01303206MaRDI QIDQ684411zbMATH OpenOpenAlexFDO

Authors Frédéric Maffray, Mostafa Blidia, Pierre Duchet

Publication date 15 September 1993

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01303206

zbMATH Keywords

kernelcliquedigraphindependent setperfect graphsstrongly perfect graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Recommendations

• Kernels in perfect line-graphs
• scientific article; zbMATH DE number 4095497
• scientific article; zbMATH DE number 4095496
• Perfect graphs are kernel solvable
• A note on Duchet's conjecture

Cites work

• scientific article; zbMATH DE number 4095497 (Why is no real title available?)
• A parity digraph has a kernel
• Graphes Noyau-Parfaits
• Kernels in some orientations of comparability graphs
• On kernels and semikernels of digraphs
• On kernels in i-triangulated graphs
• Parity graphs are kernel-M-solvable
• Topics on perfect graphs

Cited in

(29)

• A note on Duchet's conjecture
• Kernels in graphs with a clique-cutset
• A corrected version of Meyniel's conjecture
• Stable effectivity functions and perfect graphs
• Kernels by monochromatic paths in digraphs with covering number 2
• On kernel-perfect orientations of line graphs
• scientific article; zbMATH DE number 4095496 (Why is no real title available?)
• Perfect graphs are kernel solvable
• A new characterization of perfect graphs
• Kernels and perfectness in arc-local tournament digraphs
• A family of counterexamples for a conjecture of Berge on \(\alpha\)-diperfect digraphs
• Perfect graphs, kernels, and cores of cooperative games
• Perfectly orderable graphs and almost all perfect graphs are kernel \(M\)- solvable
• On 2-dominating kernels in graphs
• A theorem about a conjecture of H. Meyniel on kernel-perfect graphs
• Perfect digraphs
• Parity graphs are kernel-M-solvable
• scientific article; zbMATH DE number 6194066 (Why is no real title available?)
• Characterization of asymmetric CKI- and KP-digraphs with covering number at most 3
• scientific article; zbMATH DE number 4095497 (Why is no real title available?)
• On kernel-less clique-acyclic orientations of minimally imperfect graphs
• \(B_ 1\)- and \(B_ 2\)-orientable graphs in kernel theory
• Kernels in perfect line-graphs
• Recent problems and results about kernels in directed graphs
• Kernels in a special class of digraphs
• On the orientation of meyniel graphs
• On kernels in i-triangulated graphs
• On the kernel and related problems in interval digraphs
• Perfect graphs with polynomially computable kernels

This page was built for publication: On kernels in perfect graphs

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