Magnant–Wang–Yuan path-cover conjecture for graphs with prescribed degree bounds
For a graph , let denote the minimum number of vertex-disjoint paths needed to cover . Let , and write and for the maximum and minimum degrees.
Magnant–Wang–Yuan's conjecture. The path-cover number satisfies
The bound is tight for disjoint unions of and of . The conjecture is known when and when , but remains open in general according to the source.
References
Primary source
Allan Lo, Viresh Patel and Mehmet Akif Yıldız, “Cycle Partitions in Dense Regular Digraphs and Oriented Graphs”, arXiv:2309.11677 (2025).
Additional references
2 papers in this index state this conjecture (2018–2023). The statement above is taken from the most recent of them; the others are arXiv:1807.10613.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.