Premium
A sufficient condition for a digraph to be kernel‐perfect
Author(s) -
Duchet P.
Publication year - 1987
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190110112
Subject(s) - digraph , mathematics , combinatorics , kernel (algebra) , set (abstract data type) , directed graph , discrete mathematics , computer science , programming language
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.