← All problems

Magnant–Wang–Yuan path-cover conjecture for graphs with prescribed degree bounds

8 years old · traced to

For a graph GG, let π(G)\pi(G) denote the minimum number of vertex-disjoint paths needed to cover V(G)V(G). Let n=∣V(G)∣n=|V(G)|, and write Δ(G)=Δ\Delta(G)=\Delta and δ(G)=δ\delta(G)=\delta for the maximum and minimum degrees.

Magnant–Wang–Yuan's conjecture. The path-cover number satisfies

π(G)≤max⁡{nδ+1,(Δ−δ)nΔ+δ}.\pi(G)\leq \max\left\{\frac{n}{\delta+1},\frac{(\Delta-\delta)n}{\Delta+\delta}\right\}.

The bound is tight for disjoint unions of Kδ+1K_{\delta+1} and of Kδ,ΔK_{\delta,\Delta}. The conjecture is known when δ≤2\delta\leq 2 and when Δ≥2δ\Delta\geq 2\delta, but remains open in general according to the source.

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.

Source: Allan Lo, Viresh Patel and Mehmet Akif Yıldız, “Cycle Partitions in Dense Regular Digraphs and Oriented Graphs”, arXiv:2309.11677 (2025).

Progress summary

Never refreshed

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.