Orientations of graphs in kernel theory
type: Item
instance of: scholarly article
title: Orientations of graphs in kernel theory
zbMATH Open document ID: 0732.05044
DOI: 10.1016/0012-365X(91)90136-P
published in: Discrete Mathematics
publication date: 1991-01-01T00:00:00Z
review text: The strong perfect-graph conjecture of Berge reads as follows: A graph G is perfect iff G does not contain \(C_{2n+1}\) and \(\bar C_{2n+1}\), \(n\geq 2\), as an induced subgraph. In the present paper a certain class of finite, simple graphs G is investigated which satisfy this conjecture. An orientation \(\vec G\) of G is a digraph obtained from G by orientation of each edge of G in at least one of the two possible directions, \(\vec G\) is called a normal orientation if every complete subgraph of G possesses an absorbing vertex and a kernel of \(\vec G(X,U)\) is a subset \(K\subseteq X\) such that K is independent and absorbing. The treated class of graphs - the so-called \({\mathfrak M}\)-free graphs - consists of such members which have no induced subgraph isomorphic to an element of \({\mathfrak M}=(M_ 1,M_ 2,M_ 3)\) in which \(M_ i\), \(i=1,2,3\), are special simple planar graphs which are portrayed \([M_ 1(6,6)-6\) vertices 6 edges; \(M_ 2(5,6)\); \(M_ 3(5,7)]\). In the first chapter some structural properties of these graphs and studied which especially result in equivalent statements and from Theorem 1.4 follows that \({\mathfrak M}\)-free graphs satisfy the above mentioned conjecture. In the second chapter are considered normal orientations of \({\mathfrak M}\)- free graphs and relations to the class of the so-called R-digraphs are proved (in a previous paper was shown that \(\vec G\) is an R-digraph iff every induced subdigraph of \(\vec G\) has a kernel), in which also relations to triangle-free graphs appear. The main result is the proof that \({\mathfrak M}\)-free graphs satisfy the conjecture of Berge-Duchet: A graph is perfect iff any normal orientation of G is kernel-perfect (Theorem 2.3). To prove it is used Richardson's Theorem: Any digraph which does not contain directed cycles of odd length has a kernel. Finally are considered orientations of \(K_ 4-e\) free graphs and the results of this chapter characterize the relevance of such graph classes …
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 4210184
zbMATH Keywords: structure of perfect graphs
zbMATH Keywords: problems of kernel theory
zbMATH Keywords: strong perfect- graph conjecture
author: Hortensia Galeana-Sánchez
author: V. Neumann-Lara
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
cites work: Q3941433
cites work: Q3222875
cites work: Complement reducible graphs
cites work: Graphes Noyau-Parfaits
cites work: A note on kernel-critical graphs
cites work: Une généralisation du théorème de Richardson sur l'existence de noyaux dans les graphes orientes
cites work: On kernels and semikernels of digraphs
cites work: On kernel-perfect critical digraphs
cites work: Extending kernel perfect digraphs to kernel perfect critical digraphs
cites work: A counterexample to a conjecture of Meyniel on kernel-perfect graphs
cites work: A theorem about a conjecture of H. Meyniel on kernel-perfect graphs
cites work: Q5844986
cites work: Solutions of irreflexive relations
cites work: Extension Theorems for Solutions of Irreflexive Relations
full work available at URL: 0012-365x(91)90136-p
OpenAlex ID: W2074536685
description: scientific article; zbMATH DE number 4210184