𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A theorem about a conjecture of H. Meyniel on kernel-perfect graphs

✍ Scribed by Hortensia Galeana-Sánchez

Publisher
Elsevier Science
Year
1986
Tongue
English
Weight
391 KB
Volume
59
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

A digraph D is said to be an R-digraph (kernel-perfect graph) if all of its induced subdigraphs possesses a kernel (independent dominating subset).

I show in this work that a digraph D, without directed triangles all of whose odd directed cycles C = (1, 2,..., 2n + 1, 1), possesses two short chords (that means there exist two arcs of D of the form: (q, q + 2) and (q', q' + 2)) is an R-digraph.

📜 SIMILAR VOLUMES

On a class of kernel-perfect and kernel-
On a class of kernel-perfect and kernel-perfect-critical graphs
✍ Kiran B. Chilakamarri; Peter Hamburger 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 275 KB

Chilakamarri, K.B. and P. Hamburger, On a class of kernel-perfect and kernel-perfect-critical graphs, Discrete Mathematics 118 (1993) 253-257. In this note we present a construction of a class of graphs in which each of the graphs is either kernel-perfect or kernel-perfect-critical. These graphs or

Proof of a conjecture on irredundance pe
Proof of a conjecture on irredundance perfect graphs
✍ Lutz Volkmann; Vadim E. Zverovich 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 157 KB 👁 1 views

## Abstract Let __ir__(__G__) and γ(__G__) be the irredundance number and the domination number of a graph __G__, respectively. A graph __G__ is called __irredundance perfect__ if __ir__(__H__)=γ(__H__), for every induced subgraph __H__ of __G__. In this article we present a result which immediatel

On a theorem about vertex colorings of g
On a theorem about vertex colorings of graphs
✍ Claudio Bernardi 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 121 KB

Lawrence [2, Theorem 3] and Borodin and Kostochka [1, Lemma 2' 1 both give the same theorem about vertex colorings of graphs (Corollary 1 below). But Lawrence's proof, although powerful, is a little long, and Borodin and Kostoehka state the result without a proof.

On a problem of G. Hahn about coloured h
On a problem of G. Hahn about coloured hamiltonian paths in K2t
✍ M. Maamoun; H. Meyniel 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 209 KB

We prove a theorem &wing that for every ir teger p (p a2) there is a good minirlal coloring of the edges alf JCzD such that every hamiltonian path in Kzp uses at least one colour twice. Tphis gives a counter-example tea a conjecture of Ha III [2).