On kernels in perfect graphs

DOI10.1007/BF01303206zbMATH Open0780.05020OpenAlexW1983199480MaRDI QIDQ684411FDOQ684411

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

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

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)

Cites Work

• Title not available (Why is that?)
• Graphes Noyau-Parfaits
• On kernels and semikernels of digraphs
• Topics on perfect graphs
• A parity digraph has a kernel
• Parity graphs are kernel-M-solvable
• On kernels in i-triangulated graphs
• Kernels in some orientations of comparability graphs

Cited In (29)

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

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)