On the orientation of meyniel graphs
Mostaffa Blidia, Pierre Duchet, Frédéric Maffray · Journal of Graph Theory · 1994
Abstract A kernel of a directed graph is a set of vertices K that is both absorbant 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 endpoints 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 conjecture holds for all graphs in which every odd cycle has two chords.