A characterization of normal fraternally orientable perfect graphs (Q1357743): Difference between revisions

A digraph \(D= (V(D),A(D))\) is called a fraternal orientation of a graph \(G\) if \(u\to w\), \(v\to w\in A(D)\) implies that at least one of the arcs \(u\to v\), \(v\to u\) is in \(A(D)\). This definition is somewhat misleading since we normally do not allow directed cycles of length 2 in orientations of graphs. Another, in the reviewer's opinion, better name for such a digraph is the term in-semicomplete: it is easy to see that if \(D\) satisfies the condition above, then for every vertex \(v\in V(D)\) the set of in-neighbours of \(v\) induce a semicomplete digraph (i.e., a digraph with no pair of nonadjacent vertices). A kernel of a digraph \(D\) is a set of vertices which satisfies: (i) The digraph induced by \(X\) has no arcs. (ii) For every \(z\in V(D)\backslash X\) there exists \(x\in X\) such that \(z\to x\) is an arc of \(D\). A digraph \(D\) is kernel-perfect if every induced subgraph of \(D\) has a kernel. It is easy to see that every semicomplete induced subgraph of a kernel-perfect digraph must have an absorbing vertex (i.e., a vertex which is an out-neighbour of every other vertex). A digraph \(D_G\) is called a normal orientation of \(G\) if every semisimple induced subgraph of \(D\) has an absorbing vertex. A conjecture of Berge and Duchet states that a graph \(G\) is perfect if and only if every normal orientation of \(G\) is kernel-perfect. In this paper, the author proves a variant of this conjecture for the case when \(G\) allows a normal fraternal orientation.