𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the orientation of meyniel graphs

✍ Scribed by Mostaffa Blidia; Pierre Duchet; Frédéric Maffray

Publisher
John Wiley and Sons
Year
1994
Tongue
English
Weight
360 KB
Volume
18
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

On the oriented chromatic index of orien
On the oriented chromatic index of oriented graphs
✍ Pascal Ochem; Alexandre Pinlou; Éric Sopena 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 227 KB

## Abstract A homomorphism from an oriented graph __G__ to an oriented graph __H__ is a mapping $\varphi$ from the set of vertices of __G__ to the set of vertices of __H__ such that $\buildrel {\longrightarrow}\over {\varphi (u) \varphi (v)}$ is an arc in __H__ whenever $\buildrel {\longrightarrow}

On Deeply Critical Oriented Graphs
On Deeply Critical Oriented Graphs
✍ O.V. Borodin; D. Fon-Der-Flaass; A.V. Kostochka; A. Raspaud; E. Sopena 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 96 KB

For every positive integer k, we present an oriented graph G k such that deleting any vertex of G k decreases its oriented chromatic number by at least k and deleting any arc decreases the oriented chromatic number of G k by two.

On Meyniel's conjecture of the cop numbe
On Meyniel's conjecture of the cop number
✍ Linyuan Lu; Xing Peng 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB

## Abstract Meyniel conjectured that the cop number __c__(__G__) of any connected graph __G__ on __n__ vertices is at most for some constant __C__. In this article, we prove Meyniel's conjecture in special cases that __G__ has diameter 2 or __G__ is a bipartite graph of diameter 3. For general con

The chromatic number of oriented graphs
The chromatic number of oriented graphs
✍ Sopena, Eric 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB 👁 2 views

We introduce in this paper the notion of the chromatic number of an oriented graph G (that is of an antisymmetric directed graph) defined as the minimum order of an oriented graph H such that G admits a homomorphism to H. We study the chromatic number of oriented k-trees and of oriented graphs with