On claw‐free M‐oriented critical kernel‐imperfect digraphs
Hortensia Galeana‐Sánchez · Journal of Graph Theory · 1996
A kernel of a digraph D is an independent and dominating set of vertices of D. A chord of a directed cycle C = (0, 1,…,n, 0) is an arc ij of D not in C with both terminal vertices in C. A diagonal of C is a chord ij with j ≠ i − 1. Meyniel made the conjecture (now know to be false) that if D is a diagraph such that every odd directed cycle has at least two chords then D has a kernel. Here we obtain some properties of claw-free M-oriented critical kernel-imperfect digraphs. As a consequence we show that if D is an M-oriented K1,3-free digraph such that every odd directed cycle of length at least five has two diagonals then D has a kernel. © 1996 John Wiley & Sons, Inc.