# Kernel perfect and critical kernel imperfect digraphs structure

Abstract : A kernel $N$ of a digraph $D$ is an independent set of vertices of $D$ such that for every $w \in V(D)-N$ there exists an arc from $w$ to $N$. If every induced subdigraph of $D$ has a kernel, $D$ is said to be a kernel perfect digraph. Minimal non-kernel perfect digraph are called critical kernel imperfect digraph. If $F$ is a set of arcs of $D$, a semikernel modulo $F$, $S$ of $D$ is an independent set of vertices of $D$ such that for every $z \in V(D)- S$ for which there exists an $Sz-$arc of $D-F$, there also exists an $zS-$arc in $D$. In this talk some structural results concerning critical kernel imperfect and sufficient conditions for a digraph to be a critical kernel imperfect digraph are presented.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [8 references]

https://hal.inria.fr/hal-01184456
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Monday, August 17, 2015 - 10:48:10 AM
Last modification on : Thursday, May 11, 2017 - 1:02:53 AM
Long-term archiving on: : Wednesday, April 26, 2017 - 9:47:16 AM

### File

dmAE0151.pdf
Publisher files allowed on an open archive

### Citation

Hortensia Galeana-Sánchez, Mucuy-Kak Guevara. Kernel perfect and critical kernel imperfect digraphs structure. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.257-262, ⟨10.46298/dmtcs.3467⟩. ⟨hal-01184456⟩

Record views