Almost equitable factorization conjecture with controlled parity defects

About 2 years old · traced to

Let kk be a positive integer, let ε1,…,εk\varepsilon_1,\ldots,\varepsilon_k be nonnegative real numbers satisfying

ε1+⋯+εk=1,\varepsilon_1+\cdots+\varepsilon_k=1,

and let GG be a graph. An edge-decomposition into factors is a decomposition of E(G)E(G) into the edge sets of factors G1,…,GkG_1,\ldots,G_k. For each vertex vv, let jvj_v denote an index whose factor has odd degree at vv, when such an index exists.

Almost equitable factorization conjecture. The graph GG can be edge-decomposed into factors G1,…,GkG_1,\ldots,G_k such that, for every v∈V(G)v\in V(G),

∣dGi(v)−εidG(v)∣<2(1≤i≤k),\left|d_{G_i}(v)-\varepsilon_i d_G(v)\right|<2\qquad(1\le i\le k),

and at most one factor has odd degree at vv. In particular, no such index exists when dG(v)d_G(v) is even. Furthermore, if GG is odd-⌈1/ε1⌉\lceil 1/\varepsilon_1\rceil-edge-connected, then jv=1j_v=1 for every odd-degree vertex vv.

The source says that the conjecture is proved when almost all proportions are equal, except possibly ε1\varepsilon_1, and that a weaker version with upper bound 66 is confirmed. The full statement remains open.

References

Primary source

Morteza Hasanvand, “Equitable factorizations of highly edge-connected graphs: complete characterizations”, arXiv:2408.16143 (2024).

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.