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

From papers

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.

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

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.

Solutions 0

No solutions have been posted yet.