Geodesic
Paths and stability number in digraphs
The electronic journal of combinatorics, Tome 16 (2009) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

The Gallai-Milgram theorem says that the vertex set of any digraph with stability number $k$ can be partitioned into $k$ directed paths. In 1990, Hahn and Jackson conjectured that this theorem is best possible in the following strong sense. For each positive integer $k$, there is a digraph $D$ with stability number $k$ such that deleting the vertices of any $k-1$ directed paths in $D$ leaves a digraph with stability number $k$. In this note, we prove this conjecture.
DOI : 10.37236/261
Classification : 05C20, 05C38, 05C55
Mots-clés : Gallai Milgram theorem, directed pths, vertex set partition, stability, dograph 
@article{10_37236_261,
     author = {Jacob Fox and Benny Sudakov},
     title = {Paths and stability number in digraphs},
     journal = {The electronic journal of combinatorics},
     year = {2009},
     volume = {16},
     number = {1},
     doi = {10.37236/261},
     zbl = {1185.05073},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/261/}
}
TY  - JOUR
AU  - Jacob Fox
AU  - Benny Sudakov
TI  - Paths and stability number in digraphs
JO  - The electronic journal of combinatorics
PY  - 2009
VL  - 16
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/261/
DO  - 10.37236/261
ID  - 10_37236_261
ER  - 
%0 Journal Article
%A Jacob Fox
%A Benny Sudakov
%T Paths and stability number in digraphs
%J The electronic journal of combinatorics
%D 2009
%V 16
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/261/
%R 10.37236/261
%F 10_37236_261
Jacob Fox; Benny Sudakov. Paths and stability number in digraphs. The electronic journal of combinatorics, Tome 16 (2009) no. 1. doi: 10.37236/261

Cité par Sources :