Laborde–Payan–Xuong conjecture on independent sets meeting longest paths

From papers

Let DD be a digraph, and call a set of vertices independent if no two of its vertices are joined by an arc. A path in DD is longest if it has maximum length among all paths in DD. 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

No solutions have been posted yet.