✦ LIBER ✦

On kernels in i-triangulated graphs

✍ Scribed by F Maffray

Publisher: Elsevier Science
Year: 1986
Tongue: English
Weight: 319 KB
Volume: 61
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(86)90095-6

No coin nor oath required. For personal study only.

✦ Synopsis

A directed graph is said to be kernel-perfect if every induced subgraph possesses a kernel (independent, absorbing subset). A necessary condition for a graph to be kernel-perfect is that every complete subgraph C has an absorbing vertex (i.e., a successor of all vertices of C). In this work, we show that this condition is sufficient for/-triangulated graphs, where every odd cycle has two non-crossing chords.

This result appears as a special case of a general relationship between the notion of kernel-perfectness and the well known strong perfect graph conjecture of Berge.

📜 SIMILAR VOLUMES

On kernels in strongly connected graphs

✍ M. Anciaux-Mundeleer; P. Hansen 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 204 KB

Spanning triangulations in graphs

✍ Daniela Kühn; Deryk Osthus 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 467 KB

## Abstract We prove that every graph of sufficiently large order __n__ and minimum degree at least 2__n__/3 contains a triangulation as a spanning subgraph. This is best possible: for all integers __n__, there are graphs of order __n__ and minimum degree ⌈2__n__/3⌉ − 1 without a spanning triangul

Kernels in random graphs

✍ W.Fernandez de la Vega 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 214 KB

For each fixed p, the random directed graph D(n, p) on n vertices with (directed) edge probability p possesses a kernel with probability tending to 1 as n + a. Pour chaque p fixe, le graphe alCatoire D(n, p) a n sommets et probabilitts des arcs Cgales B p posstde un noyau avec une probabilit6 tenda

On the existence of kernels and h-kernel

On the existence of kernels and h-kernels in directed graphs

✍ H. Galeana-Sánchez 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 272 KB

A note on kernel-critical graphs

✍ Pierre Duchet; Henri Meyniel 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 410 KB

Triangulated edge intersection graphs of

Triangulated edge intersection graphs of paths in a tree

✍ Maciej M. Sysło 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 268 KB