Strong arboricity versus arboricity conjecture
Strong arboricity versus arboricity conjecture
Let be a graph. Write for its arboricity, the least number of colors in an edge coloring with no monochromatic cycle, and write 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 satisfies
For complete graphs, the paper notes that , 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
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.