ON THE ORIENTATION OF MEYNIEL GRAPHS

A kernel of a directed graph is a set of vertices K that is both absor bant and independent (i.e., every vertex not in K is the origin of an arc whose extremity is in K, and no arc of the graph has both endpoint s in K). In 1983, Meyniel conjectured that any perfect graph, directed in such a way that every circuit of length three uses two reversible arcs, must have a kernel. This conjecture was proved for parity graphs . In this paper, we extend that result and prove that Meyniel's conjec ture holds for all graphs in which every odd cycle has two chords. (C) 1994 John Wiley & Sons, Inc.