Diperfect graphs |
| |
Authors: | Claude Berge |
| |
Affiliation: | (1) Centre de Mathématique Sociale, 54 Boulevard Raspail, 75270 Paris Cedex 06, France |
| |
Abstract: | Gallai and Milgram have shown that the vertices of a directed graph, with stability number α(G), can be covered by exactly α(G) disjoint paths. However, the various proofs of this result do not imply the existence of a maximum stable setS and of a partition of the vertex-set into paths μ1, μ2, ..., μk such tht |μi ∩S|=1 for alli. Later, Gallai proved that in a directed graph, the maximum number of vertices in a path is at least equal to the chromatic number; here again, we do not know if there exists an optimal coloring (S 1,S 2, ...,S k) and a path μ such that |μ ∩S i|=1 for alli. In this paper we show that many directed graphs, like the perfect graphs, have stronger properties: for every maximal stable setS there exists a partition of the vertex set into paths which meet the stable set in only one point. Also: for every optimal coloring there exists a path which meets each color class in only one point. This suggests several conjecties similar to the perfect graph conjecture. Dedicated to Tibor Gallai on his seventieth birthday |
| |
Keywords: | 05 C 20 05 C 15 |
本文献已被 SpringerLink 等数据库收录! |
|