The (2k1)(2k-1)-edge-connected bounded-out-degree orientation conjecture

From papers

Let GG be a graph, let kk be an integer with k3k\ge 3, and let p:V(G)Zkp:V(G)\rightarrow Z_k satisfy

E(G)kvV(G)p(v).|E(G)| \stackrel{k}{\equiv} \sum_{v\in V(G)}p(v).

A pp-orientation is an orientation satisfying the prescribed modulo-kk out-degree conditions encoded by pp. The (2k1)(2k-1)-edge-connected bounded-out-degree conjecture. If GG is (2k1)(2k-1)-edge-connected, then GG has a pp-orientation such that, for every vertex vv,

dG(v)2(k1)dG+(v)dG(v)2+(k1).\left\lfloor\frac{d_G(v)}{2}\right\rfloor-(k-1)\le d_G^+(v)\le \left\lceil\frac{d_G(v)}{2}\right\rceil+(k-1).

Furthermore, for an arbitrary vertex z0z_0, dG+(z0)d_G^+(z_0) can be assigned any plausible integer value in this interval. This would improve the edge-connectivity required by the preceding result from 2k2k to 2k12k-1; the conjecture is presented as qualitative and remains unresolved in the supplied text.

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

Morteza Hasanvand, “Modulo orientations with bounded out-degrees”, arXiv:1702.07039 (2022).

Solutions 0

No solutions have been posted yet.