pipette
ENEnglish

Tree packing and the graphic Additive Base Conjecture

Amir Jafari

Preprint

En palabras de los autores

Tutte's flow conjectures ask when a graph has a nowhere-zero flow with small integer values. We approach these questions through spanning-tree packing. A common analytic argument recovers Seymour's six-flow theorem, the three-flow theorem for six-edge-connected graphs, and the four-flow theorem for graphs with two edge-disjoint spanning trees. Its main new consequence is a prescribed-orientation theorem: for every integer , edge-disjoint spanning trees suffice to realize every compatible outdegree prescription modulo . For odd prime moduli this proves the graphic Additive Base Conjecture. A version with prescribed ranges of edge values gives sharp circular-flow bounds from tree packing and a bound in terms of cycle rank that is strictly below six for connected bridgeless graphs. We also examine a reformulation of the five-flow conjecture on graphs obtained by tripling every edge of a three-edge-connected cubic graph. A -vertex graph with fractional spanning-tree packing number and no modulo-five orientation shows that packing greater than alone does not guarantee such an orientation for arbitrary graphs. The proof combines the minimization method of Alon, Buci\'c, and Davies with integral rounding.

Resultado principalLimitación que admiten los autores

Apareció: miércoles, 7 de octubre. arXiv. Preprint, todavía sin revisión por pares.