✦ LIBER ✦

Recent problems and results about kernels in directed graphs

✍ Scribed by C. Berge; P. Duchet

Publisher: Elsevier Science
Year: 1990
Tongue: English
Weight: 355 KB
Volume: 86
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(90)90346-j

No coin nor oath required. For personal study only.

✦ Synopsis

In Section 1, we survey the existence theorems for a kernel; in Section 2, we discuss a new conjecture which could constitute a bridge between the kernel problems and the perfect graph conjecture.

In fact, we believe that a graph is 'quasi-perfect' if and only if it is perfect.

Proposition 1.1. Let G be a graph such that every odd circuit has all its arcs belonging to pairs of parallel arcs ('double-edges').

Then G is kernel-perfect.

📜 SIMILAR VOLUMES

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 survey: Recent results, conjectures, a

A survey: Recent results, conjectures, and open problems in labeling graphs

✍ Joseph A. Gallian 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 752 KB

In this paper we organize and summarize much of the work done on graceful and harmonious labelings of graphs. Many open problems and conjectures are included.

On the Ramsey multiplicities of graphs—p

On the Ramsey multiplicities of graphs—problems and recent results

✍ Stefan A. Burr; Vera Rosta 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 610 KB

## Abstract Ramsey's theorem guarantees that if __G__ is a graph, then any 2‐coloring of the edges of a large enough complete graph yields a monochromatic copy of __G__. Interesting problems arise when one asks how many such __G__ must occur. A survey of this and related problems is given, along wi

About colorings, stability and paths in

About colorings, stability and paths in directed graphs

✍ Henry Meyniel 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 191 KB

Some recent results in hamiltonian graph

Some recent results in hamiltonian graphs

✍ L. Lesniak-Foster 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 505 KB

## Abstract A variety of recent developments in hamiltonian theory are reviewed. In particular, several sufficient conditions for a graph to be hamiltonian, certain hamiltonian properties of line graphs, and various hamiltonian properties of powers of graphs are discussed. Furthermore, the concept

The end structure of a graph: recent res

The end structure of a graph: recent results and open problems

✍ Reinhard Diestel 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 1022 KB

This paper aims to give a brief introduction to a set of problems, old and new, concerned with one of the main and long-standing quests in infinite graph theory: how to represent the end structure of a given graph by that of a simpler subgraph, in particular a spanning tree. There has been a fair am