On a class of kernel-perfect and kernel-perfect-critical graphs
type: Item
instance of: scholarly article
title: On a class of kernel-perfect and kernel-perfect-critical graphs
zbMATH Open document ID: 0782.05035
DOI: 10.1016/0012-365X(93)90068-5
author: Kiran B. Chilakamarri
author: Peter Hamburger
published in: Discrete Mathematics
publication date: 1994-02-24T00:00:00Z
review text: Let \(G=(V,E)\) be a directed graph. Then a set \(K\) of its vertices is called a kernel if \(K\) is an independent set, and \(K\cap \Gamma^{- 1}(K)=\varnothing\), \(K\cup\Gamma^{-1}(K)=V\), where \(\Gamma^{-1}(K)\) is the set of all the vertices \(x\) of \(G\) such that there exists \(y\in K\) with \((x,y)\) being an arc of \(G\). \(G\) is called a kernel-perfect graph if all induced subgraphs of \(G\), including \(G\), have a kernel, and it is called a kernel-perfect-critical graph if \(G\) does not have a kernel but every proper induced subgraph has. In the paper a new construction of both kernel-perfect graphs and kernel-perfect-critical graphs is presented.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 417444
zbMATH Keywords: directed graph
zbMATH Keywords: kernel
zbMATH Keywords: kernel-perfect graph
zbMATH Keywords: kernel-perfect-critical graph
reviewed by: Peter Horák
MaRDI profile type: Publication
cites work: Q5844986
cites work: Q3941433
cites work: On kernel-perfect critical digraphs
cites work: A note on kernel-critical graphs
cites work: Graphes Noyau-Parfaits
full work available at URL: 0012-365x(93)90068-5
OpenAlex ID: W2035216900
description: scientific article; zbMATH DE number 417444