On kernels in i-triangulated graphs
type: Item
instance of: scholarly article
title: On kernels in i-triangulated graphs
zbMATH Open document ID: 0617.05029
DOI: 10.1016/0012-365X(86)90095-6
author: Frédéric Maffray
published in: Discrete Mathematics
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 3999956
zbMATH Keywords: kernel-perfect digraph
zbMATH Keywords: normal orientation
zbMATH Keywords: i-triangulated graph
reviewed by: R. C. Entringer
MaRDI profile type: Publication
cites work: Q3941433
cites work: Q3222875
cites work: On the orientation of meyniel graphs
cites work: Q3222886
cites work: Parity graphs are kernel-M-solvable
cites work: On kernels and semikernels of digraphs
cites work: Q5341588
cites work: On the perfect graph conjecture
cites work: Solutions of irreflexive relations
cites work: Q5659563
description: scientific article; zbMATH DE number 3999956