Some results on the structure of kernel-perfect and critical kernel-imperfect digraphs

DOI10.1016/J.DAM.2015.05.037MaRDI QIDQ299098zbMATH OpenOpenAlexFDO

Authors Hortensia Galeana-Sánchez, Mucuy-kak Guevara

Publication date 22 June 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2015.05.037

zbMATH Keywords

kerneldominationkernel-perfect digraphcritical kernel-imperfect digraphsemikernel modulo \(F\)

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Kernel perfect and critical kernel imperfect digraphs structure
• New classes of critical kernel-imperfect digraphs
• New extensions of kernel perfect digraphs to kernel imperfect critical digraphs
• On kernel-perfect critical digraphs
• A new method to extend kernel-perfect graphs to kernel-perfect critical graphs

Cites work

• scientific article; zbMATH DE number 3902654 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 3448611 (Why is no real title available?)
• scientific article; zbMATH DE number 3405983 (Why is no real title available?)
• scientific article; zbMATH DE number 3106184 (Why is no real title available?)
• A combinatorial theorem on ordered circular sequences of \(n_1\) \(u\)'s and \(n_2\) \(v\)'s with application to kernel-perfect graphs
• A counterexample to a conjecture of Meyniel on kernel-perfect graphs
• A note on kernel-critical graphs
• A sufficient condition for a digraph to be kernel-perfect
• A sufficient condition for kernel perfectness of a digraph in terms of semikernels modulo F
• Combinatorial games: Selected bibliography with a succinct gourmet introduction
• Graphes Noyau-Parfaits
• On kernel-perfect critical digraphs
• On kernels and semikernels of digraphs
• On monochromatic paths in edge-coloured digraphs
• On weakly ordered systems
• Perfect graphs, kernels, and cores of cooperative games
• Planar kernel and Grundy with d 3, dout 2, din 2 are NP- complete
• Recent problems and results about kernels in directed graphs
• Semikernels modulo \(F\) and kernels in digraphs
• Some sufficient conditions for the existence of kernels in infinite digraphs

Cited in

(17)

• Kernel perfect and critical kernel imperfect digraphs structure
• KP-digraphs and CKI-digraphs satisfying the k-Meyniel's condition
• A sufficient condition for kernel perfectness of a digraph in terms of semikernels modulo F
• Kernels in digraphs that are not kernel perfect
• Critical kernel imperfect problem in generalizations of bipartite tournaments
• On (k,l)-perfectnees of Special Classes of Digraphs
• On kernel-perfect critical digraphs
• A combinatorial theorem on ordered circular sequences of \(n_1\) \(u\)'s and \(n_2\) \(v\)'s with application to kernel-perfect graphs
• Some sufficient conditions on odd directed cycles of bounded length for the existence of a kernel
• Kernels by rainbow paths in arc-colored tournaments
• Solving the kernel perfect problem by (simple) forbidden subdigraphs for digraphs in some families of generalized tournaments and generalized bipartite tournaments
• New extensions of kernel perfect digraphs to kernel imperfect critical digraphs
• On kernels in strongly game-perfect digraphs and a characterisation of weakly game-perfect digraphs
• A sufficient condition for a digraph to be kernel-perfect
• Infinite kernel perfect digraphs
• Unions of digraphs which become kernel perfect
• New classes of critical kernel-imperfect digraphs

This page was built for publication: Some results on the structure of kernel-perfect and critical kernel-imperfect digraphs

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