Kernels in graphs with a clique-cutset (Q1923523): Difference between revisions

Let \(G\) be a finite directed graph without multiple arcs or loops. A kernel of \(G\) is a subset \(K\) of vertices with the following properties: (1) every vertex of \(G - K\) has a successor in \(K\), and (2) there is no arc between any two vertices of \(K\). Not every \(G\) admits a kernel, but many conditions are known that imply the existence of a kernel. \(G\) is called kernel-perfect if every induced subgraph has a kernel. To investigate what kind of graph constructions preserve kernel-perfectness, the concept of clique-cutset is introduced. A clique-cutset \(C\) is a subset of vertices such that \(C\) is a clique and \(G - C\) is disconnected. For every connected component \(A\) of \(G - C\), the subgraph induced by \(A \cup C\) is called a piece of \(G\) with respect to \(C\). The author obtains the following result: Let \(G\) be a directed graph which admits a clique-cutset \(C\). Then \(G\) is kernel-perfect iff every piece of \(G\) with respect to \(C\) is kernel-perfect (Theorem 1).