Almost equitable factorization conjecture with controlled parity defects

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 vV(G)v\in V(G),

dGi(v)εidG(v)<2(1ik),\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.

Sources & referencesView supporting material

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.