Strong arboricity versus arboricity conjecture

Let GG be a graph. Write arb(G)\operatorname{arb}(G) for its arboricity, the least number of colors in an edge coloring with no monochromatic cycle, and write ζ(G)\zeta(G) for its strong arboricity, the least number of colors in a coloring that remains acyclic after contracting any single edge.

Strong arboricity conjecture. Every graph GG satisfies

ζ(G)2arb(G).\zeta(G)\leqslant 2\operatorname{arb}(G).

For complete graphs, the paper notes that ζ(Kn)=2arb(Kn)1\zeta(K_n)=2\operatorname{arb}(K_n)-1, motivating this proposed general upper bound.

Sources & referencesView supporting material

Primary source

Tomasz Bartnicki, Sebastian Czerwiński, Jarosław Grytczuk and Zofia Miechowicz, “Strong arboricity of graphs”, arXiv:2303.08771 (2023).

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.