Laborde–Payan–Xuong conjecture on independent sets meeting longest paths
Laborde–Payan–Xuong conjecture on independent sets meeting longest paths
Let be a digraph, and call a set of vertices independent if no two of its vertices are joined by an arc. A path in is longest if it has maximum length among all paths in . Laborde–Payan–Xuong conjecture. Every digraph has an independent set meeting every longest path. The conjecture is presented as an open problem from 1983; the paper does not state a resolution in the supplied text.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Germán Benítez-Bobadilla, Hortensia Galeana-Sánchez and César Hernández-Cruz, “Long-eared digraphs”, arXiv:2504.01918 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.