On kernels in i-triangulated graphs

A kernel of a digraph D is a subset K of V(D) such that no vertex in K is adjacent to a vertex in K and every vertex in V(D)\(\setminus K\) is adjacent to some vertex in K. If every induced subdigraph of D possesses a kernel, D is called kernel-perfect. Thus every complete subdigraph of a kernel-perfect digraph must have a vertex to which all others are adjacent. A digraph D is called a normal orientation of the graph \(D^*\) if every complete subdigraph of D has vertex to which all others are adjacent. A graph is said to be i-triangulated if every elementary cycle of odd length at least 5 has two non-crossing chords. The author shows that an orientation of an i-triangulated graph is kernel-perfect iff it is a normal orientation. This result is relevant to a conjecture of Berge and Duchet stating that a graph G is perfect iff any normal orientation of G is kernel-perfect.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: On kernels in i-triangulated graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1821791)