Strong arboricity versus arboricity conjecture

About 3 years old · traced to

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.

References

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.