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

At least 8 years old · documented by

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

∣E(G)∣≡k∑v∈V(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 (2k−1)(2k-1)-edge-connected bounded-out-degree conjecture. If GG is (2k−1)(2k-1)-edge-connected, then GG has a pp-orientation such that, for every vertex vv,

⌊dG(v)2⌋−(k−1)≤dG+(v)≤⌈dG(v)2⌉+(k−1).\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 2k−12k-1; the conjecture is presented as qualitative and remains unresolved in the supplied text.

References

Primary source

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

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.