Comnnmicated by G. Berge
In [3] Galeana-Stinchez and Neumann-Lara have deveioped a genera! method to extend kernel-perfect graphs to kernel-perfect critical graphs. In this note we construct a class of kernel-perfect critical graphs which can be used to extend any kernel-perfect graph.
For general concepts we refer the reader to [I]. Let D be a digraph and denote by V(D) the set of vertices of D, and by F(D) the set of arcs of D.
(1) N E V(D) is a kernel of D iff N is independent and for every z E W there exists an arc (z, w) of D with w E N.
(2) D is said to be an R-digraph (kernel-perfect graph) iff every induced subdigraph of D has a kernel.
(3) D is said to be an R--digraph (kernel-perfect critical graph) iff every proper induced subdigraph of D has a kernel b_;t 9 does not (4) If S1 E V(D), D[&] will denote the subdigraph of D inducec' by S,. (5) Let C be a dir&ted cycle of D, if U, u E V(C) we denote by (u, C, V) the directed path from k~ to u contained in C. If f = {u, u) E F(D), D(f, Pi,) will denote any digraph D' such thzt D' = D U PJu, u), where P,(vg U) is a vu-directed path of length PI -1 satisfying V(P"(tJ, U) n D) = {V, U}.