pipette
ESEspañol

Linear arboricity conjecture for infinite graphs

Leandro Aurichi, Rodrigo Santos Monteiro, Caio Fernando Rodrigues

Preprint

In the authors' words

The linear arboricity of a graph is the least cardinality of linear forests, that is, forests of maximum degree at most , into which its edge set can be decomposed. The Linear Arboricity Conjecture asserts that for every finite graph , where denotes the maximum degree of . We extend this conjecture to infinite graphs of finite maximum degree and prove that its finite and infinite versions are equivalent. We introduce topological linear arboricity by requiring the linear forests to contain no topological circle, and show that it differs from linear arboricity by at most one. Finally, we prove that every -regular graph of girth at least has topological linear arboricity at most .

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 2. arXiv. Preprint, not yet peer-reviewed.