✦ LIBER ✦

On Deeply Critical Oriented Graphs

✍ Scribed by O.V. Borodin; D. Fon-Der-Flaass; A.V. Kostochka; A. Raspaud; E. Sopena

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 96 KB
Volume: 81
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2000.1984

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

On critically perfect graphs

✍ Wagler, Annegret 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 337 KB 👁 2 views

A perfect graph is critical, if the deletion of any edge results in an imperfect graph. We give examples of such graphs and prove some basic properties. We relate critically perfect graphs to well-known classes of perfect graphs, investigate the structure of the class of critically perfect graphs, a

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 the critical graph conjecture

✍ Hian Poh Yap 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 222 KB

## Abstract Gol'dberg has recently constructed an infinite family of 3‐critical graphs of even order. We now prove that if there exists a __p__(≥4)‐critical graph __K__ of odd order such that __K__ has a vertex __u__ of valency 2 and another vertex __v__ ≠ __u__ of valency ≤(__p__ + 2)/2, then ther

On the critical point-arboricity graphs

✍ Riste Škrekovski 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 155 KB

## Abstract In this paper, we study the critical point‐arboricity graphs. We prove two lower bounds for the number of edges of __k__‐critical point‐arboricity graphs. A theorem of Kronk is extended by proving that the point‐arboricity of a graph __G__ embedded on a surface __S__ with Euler genus __

A note on vertex pancyclic oriented grap

A note on vertex pancyclic oriented graphs

✍ Bang-Jensen, J�rgen; Guo, Yubao 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 185 KB 👁 2 views

Let D be an oriented graph of order n ≥ 9, minimum degree at least n -2, such that, for the choice of distinct vertices x and y, . Graph Theory 18 (1994), 461-468) proved that D is pancyclic. In this note, we give a short proof, based on Song's result, that D is, in fact, vertex pancyclic. This also

On the orientation of meyniel graphs

✍ Mostaffa Blidia; Pierre Duchet; Frédéric Maffray 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 360 KB

## 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,