A sufficient condition for a digraph to be kernel‐perfect
Pierre Duchet · Journal of Graph Theory · 1987
Abstract Galeana‐Sanchez and Neumann‐Lara proved that a sufficient condition for a digraph to have a kernel (i.e., an absorbent independent set) is the following: (P) every odd directed cycle possesses at least two directed chords whose terminal endpoints are consecutive on the cycle. Here it is proved that (P) is satisfied by those digraphs having these two properties: (i) the reversal of every 3‐circuit is present, and (ii) every odd directed cycle v 1 … v 2 n +1 V 1 has two chords of the form ( v i , v i+2 ). This is stronger than a result of Galeana‐Sanchez.