Orientations of graphs in kernel theory (Q809100): Difference between revisions

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 to the kernel theory.