Large-girth strong arboricity conjecture

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

Large-girth strong arboricity conjecture. For every integer kk there is an integer g(k)g(k) such that every graph GG with

arb(G)k\operatorname{arb}(G)\leqslant k

and girth at least g(k)g(k) satisfies

ζ(G)=arb(G).\zeta(G)=\operatorname{arb}(G).

The conjecture expresses the expectation that sufficiently large girth makes strong arboricity attain its smallest possible value, namely arboricity, within every bounded-arboricity class.

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).

Additional references

2 papers in this index state this conjecture (2022–2023). The statement above is taken from the most recent of them; the others are arXiv:2210.04649.

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.