Large-girth strong arboricity conjecture
Large-girth strong arboricity conjecture
Let be a graph. Its arboricity is the least number of colors in an edge coloring with no monochromatic cycle, and its strong arboricity is the least number of colors in a coloring that remains acyclic after contracting any single edge. The girth of is the length of its shortest cycle.
Large-girth strong arboricity conjecture. For every integer there is an integer such that every graph with
and girth at least satisfies
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.