Kernels in graphs with a clique-cutset
type: Item
instance of: scholarly article
title: Kernels in graphs with a clique-cutset
zbMATH Open document ID: 0856.05083
DOI: 10.1016/0012-365X(96)00018-0
published in: Discrete Mathematics
publication date: 1996-10-07T00:00:00Z
review text: 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).
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 932565
zbMATH Keywords: kernel-perfect
zbMATH Keywords: clique-cutset
zbMATH Keywords: piece
zbMATH Keywords: directed graph
author: Henry Jacob
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
cites work: Q4099676
cites work: A remark on a problem of Harary
cites work: Planar kernel and Grundy with \(d\leq 3\), \(dout\leq 2\), \(din\leq 2\) are NP- complete
cites work: Kernels in perfect line-graphs
Recommended article: Q3703918
Recommended article: Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems
Recommended article: Exploiting c-Closure in Kernelization Algorithms for Graph Problems
Recommended article: A new generalization of kernels in digraphs
Recommended article: On kernels in i-triangulated graphs
Recommended article: Kernels in a special class of digraphs
Recommended article: Q5135789
Recommended article: Kernels in weighted digraphs
Recommended article: On kernels in perfect graphs
Recommended article: Clique cutsets beyond chordal graphs
description: scientific article; zbMATH DE number 932565