The relaxed partition number conjecture

A path partition of a graph is a set of vertex-disjoint paths containing all vertices, and an isolated vertex counts as a path. For a graph GG with nn vertices, let πp(G)\pi_p(G) denote the minimum number of paths in a path partition, and let dd be its regular degree.

The relaxed partition number conjecture. For any dd-regular graph GG,

πp(G)=O(nd+1).\pi_p(G)=O\left(\frac{n}{d+1}\right).

This is a weaker asymptotic version of the partition number conjecture. The supplied text gives no resolution status.

Sources & referencesView supporting material

Primary source

Uriel Feige and Ella Fuchs, “On the path partition number of 6-regular graphs”, arXiv:1911.08397 (2019).

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.