Pullman's conjecture on strongly consistent odd-regular graphs

Let GG be a finite undirected graph. An orientation of GG is obtained by directing each edge, and GG is strongly consistent if every orientation of GG is consistent, where consistency means that the minimum number of directed paths in an edge decomposition equals the excess

ex(D)=12vV(D)d+(v)d(v).\operatorname{ex}(D)=\frac{1}{2}\sum_{v\in V(D)}\lvert d^+(v)-d^-(v)\rvert.

Pullman's conjecture. For odd dd, every dd-regular graph is strongly consistent. This generalizes the even-order tournament conjecture from complete graphs to all odd-regular graphs; the paper develops results for sparse graphs but does not resolve the conjecture in full.

Sources & referencesView supporting material

Primary source

Viresh Patel and Mehmet Akif Yıldız, “Path decompositions of oriented graphs”, arXiv:2411.06982 (2026).

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.