𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Orientations of graphs in kernel theory

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

Publisher
Elsevier Science
Year
1991
Tongue
English
Weight
589 KB
Volume
87
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we investigate structural properties of a certain class of graphs (%&free graphs) which are relevant in the study of kernel theory, m-free graphs satisfy the strong perfect graph conjecture of Berge. We investigate orientations of Z&free graphs and other classes of graphs which produce kernel-perfect digraphs.

📜 SIMILAR VOLUMES

B1- and B2-orientable graphs in kernel t
B1- and B2-orientable graphs in kernel theory
✍ H. Galeana-Sánchez 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 366 KB

In this note I prove that B, or B,-oriented digraphs satisfy the following conjecture proposed by Meyniel (1980): if every directed cycle of odd length in a digraph D has at least two pseudodiagonals then D has a kernel.

Acyclic orientations of graphs
Acyclic orientations of graphs
✍ Richard P. Stanley 📂 Article 📅 1973 🏛 Elsevier Science 🌐 English ⚖ 708 KB

## Let G be a finite graph with p vertices and x its chromatic polynomial. A combinatorial interpretation is given to the positive integer (-l)px(-A), where h is a positive integer, in terms of acyclic orientations of G. In particular, (-l)Px(-1) is the number of acyclic orientations of G. An appl

Orientations of circle graphs
Orientations of circle graphs
✍ R. C. Read; D. Rotem; J. Urrutia 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 756 KB