Originator(s): J.-M. Laborde, C. Payan, N.H. Xuong (presented by C. Stocker - REGS 2009)
Definitions: An independent set of vertices in a graph is a set of pairwise nonadjacent vertices.
Conjecture: [LPX] Every digraph has an independent set intersecting every longest path.
Strong Conjecture: [LPX] Every digraph has an independent set S that intersects every longest path and has the additional property that every vertex in S is the beginning of some longest path.
Comments: The stronger form holds when the digraph has a spanning path (take the source of any spanning path) or has no independent set of size 3 [H]. The weaker conjecture holds for all oriented bipartite graphs (take one partite set) and all orientations of complete tripartite graphs. It also holds for all tournaments (tournaments have spanning paths), and it holds when the longest paths omit exactly one vertex. The stronger form holds when longest paths have at most three vertices.
Possible special cases of interest include proving the conjecture(s) for digraphs with a fixed longest path length, digraphs whose underlying graph has a fixed chromatic number, or digraphs with various structural properties.
References:
[H] F. Havet, Stable set meeting every longest path
Discrete Math. 289 (2004), no. 1-3, 169-173.
[LPX] J.-M. Laborde, C. Payan, N.H. Xuong, Independent sets and longest directed paths in digraphs
Graphs and other combinatorial Topics Prague, 1982, Teubner, Leipzig, 1983, pp. 173-177