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

DOI10.1016/j.dam.2015.05.037zbMath1339.05286OpenAlexW1050290852MaRDI QIDQ299098

Mucuy-kak Guevara, Hortensia Galeana-Sánchez

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

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

Related Items

Kernels by rainbow paths in arc-colored tournaments

Cites Work

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