Stable set meeting all longest directed paths.

Importance: Medium ✭✭
Subject: Graph Theory
Recomm. for undergrads: no
Posted by: fhavet
on: March 1st, 2013

\begin{conjecture} Every digraph has a stable set meeting all longest directed paths \end{conjecture}

If the stability number is 1, that is if the digraph is a tournament, it follows Redei's Theorem stating that every tournament has a directed hamiltonian path. The conjecture has been proved by Havet [H] for digraphs having stability number 2.

The conjecture would give an easy inductive proof of Gallai-Roy Theorem: every digraph with chromatic number $k$ contains a directed path on $k$ vertices.

Hahn and Jackson [HJ] conjectured that in contrast there is no directed path meeting every maximum stable set. In fact, they conjectured the following: 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$. This was proved by Fox and Sudakov [FS] by a probabilistic argument.

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{}


[FS] J. Fox and B. Sudakov, Paths and stability number in digraphs, Electronic Journal of Combiantorics, 16 (2009), no.1, N23.

[HJ] G. Hahn and B. Jackson, A note concerning paths and independence number in digraphs, Discrete Math. 82 (1990), 327–329.

[H] F. Havet. Stable set meeting every longest path. Discrete Mathematics, 289 (2004), no. 1-3, 169-173.

*[LPX] J.M. Laborde, C. Payan, and N.H. Xuong, Independent sets and longest directed paths in digraphs. In Graphs and other Combinatorial Topics (Prague, 1982)}, Teubner-Texte Math., Vol. 59 (1983), 173-177, Teubner, Leipzig.

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

* indicates original appearance(s) of problem.