𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On kernel-perfect critical digraphs

✍ Scribed by H. Galeana-Sánchez; V. Neumann-Lara

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

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we investigate new sufficient conditions for a digraph to be kernel-perfect (KP) and some structural properties of kernel-perfect critical (KPC) digraphs. In particular, it is proved that the asymmetrical part of any KPC digraph is strongly connected. A new method to construct KPC digraphs is developed. The existence of KP and KPC digraphs with arbitrarily large dichromatic number is also discussed.

📜 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

On claw-freeM-oriented critical kernel-i
On claw-freeM-oriented critical kernel-imperfect digraphs
✍ Galeana-S�nchez, H. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 382 KB

A kernel of a digraph D is an independent and dominating set of vertices of D. A chord of a directed cycle C = (0, 1 , . . . , n, 0) is an arc of D not in C with both terminal vertices in C . A diagonal of C is a chord with j # i -1. Meyniel made the conjecture (now know to be false) that if D is a

A new method to extend kernel-perfect gr
A new method to extend kernel-perfect graphs to kernel-perfect critical graphs
✍ Hortensia Galeana-Sánchez 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 200 KB

## Comnnmicated by G. Berge In [3] Galeana-Stinchez and Neumann-Lara have deveioped a genera! method to extend kernel-perfect graphs to kernel-perfect critical graphs. In this note we construct a class of kernel-perfect critical graphs which can be used to extend any kernel-perfect graph. For gen