𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Kernels in some orientations of comparability graphs

✍ Scribed by Christophe Champetier

Publisher
Elsevier Science
Year
1989
Tongue
English
Weight
170 KB
Volume
47
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Orientations of graphs in kernel theory
Orientations of graphs in kernel theory
✍ H. Galeana-SΓ‘nchez; V. Neumann-Lara πŸ“‚ Article πŸ“… 1991 πŸ› Elsevier Science 🌐 English βš– 589 KB

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

Distances in orientations of graphs
Distances in orientations of graphs
✍ V ChvΓ‘tal; C Thomassen πŸ“‚ Article πŸ“… 1978 πŸ› Elsevier Science 🌐 English βš– 815 KB
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.

Sinks in Acyclic Orientations of Graphs
Sinks in Acyclic Orientations of Graphs
✍ David D. Gebhard; Bruce E. Sagan πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 183 KB

Greene and Zaslavsky proved that the number of acyclic orientations of a graph G with a unique sink at a given vertex is, up to sign, the linear coefficient of the chromatic polynomial. We give three proofs of this result using pure induction, noncommutative symmetric functions, and an algorithmic b