Paths and stability number in digraphs

Publication date 26 March 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0905.2644, https://eudml.org/doc/230739, http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1n23.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

directed pths dograph Gallai Milgram theorem stability vertex set partition

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Generalized Ramsey theory (05C55)

Abstract: 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.

Review text

Summary: 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, {ıG. Hahn} and \textit{B. Jackson} [``A note concerning paths and independence number in digraphs, Discrete Math. 82, No.\,3, 327--329 (1990; Zbl 0701.05020)] 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.

Recommendations

Cited in

(14)

This page was built for publication: Paths and stability number in digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380212)