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

DOI10.1016/J.DAM.2015.05.037zbMATH Open1339.05286OpenAlexW1050290852MaRDI QIDQ299098FDOQ299098

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On monochromatic paths in edge-coloured digraphs
• Perfect graphs, kernels, and cores of cooperative games
• Some sufficient conditions for the existence of kernels in infinite digraphs
• On kernel-perfect critical digraphs
• Planar kernel and Grundy with \(d\leq 3\), \(dout\leq 2\), \(din\leq 2\) are NP- complete
• 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
• Recent problems and results about kernels in directed graphs
• A sufficient condition for kernel perfectness of a digraph in terms of semikernels modulo \(F\)
• A sufficient condition for a digraph to be kernel-perfect
• Graphes Noyau-Parfaits
• Title not available (Why is that?)
• On kernels and semikernels of digraphs
• Combinatorial games: Selected bibliography with a succinct gourmet introduction
• A note on kernel-critical graphs
• A counterexample to a conjecture of Meyniel on kernel-perfect graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On weakly ordered systems

Cited In (11)

• 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\)
• 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
• New extensions of kernel perfect digraphs to kernel imperfect critical digraphs
• A sufficient condition for a digraph to be 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)