Premium
On the orientation of meyniel graphs
Author(s) -
Blidia Mostaffa,
Duchet Pierre,
Maffray Frédéric
Publication year - 1994
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190180706
Subject(s) - combinatorics , mathematics , conjecture , vertex (graph theory) , chordal graph , graph , discrete mathematics
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.