CHORDLESS PATHS, ODD HOLES, AND KERNELS IN GRAPHS WITHOUT M-OBSTRUCTIONS

An m-obstruction in a directed graph G(V,E) is a chordless simple path X(1), X(2),...,X(m+2) having x(1) --> x(2), x(m+2) --> x(m+1) is an e lement of E. A directed graph is fraternally oriented if it has no 1-o bstructions and it is perfectly oriented if it has no 2-obstructions. A directed graph is normal if it has no directed triangles. We describ e polynomial time algorithms for the recognition of a chordless direct ed path of a given parity between two vertices in a directed graph wit hout m-obstructions, and when m = 2(q), for the recognition of odd hol es. These are used to test whether a normal fraternally or perfectly o riented graph is perfect (assuming the Strong Perfect Graph Conjecture ). In addition, we describe a polynomial time algorithm to find a kern el in a normal fraternally oriented graph using a structural character ization of the subgraph generated by two kernels. (C) 1994 Academic Pr ess, Inc.