PreprintarXiv licencearXiv
Linear arboricity conjecture for infinite graphs
Abstract
The linear arboricity la(G) of a graph G is the least cardinality of linear forests, that is, forests of maximum degree at most $2$, into which its edge set E(G) can be decomposed. The Linear Arboricity Conjecture asserts that la(G)≤⌈(Δ(G)+1)/2⌉ for every finite graph G, where Δ(G) denotes the maximum degree of G. 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 latop (G) 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 2k-regular graph of girth at least 2k has topological linear arboricity at most k+1.
Related
- Kriesell's conjecture for infinite graphs
- Arboricity and Simplicial Geometric Category of Wedges and Joins of Graphs
- DP vertex-arboricity of sparse graphs
- Breaking the Infinite Barrier in the 1/3--2/3 Conjecture
- An infinite family of intransitive directed strongly regular graphs with rank 6 Weisfeiler--Leman closure
BibTeX
@misc{aurichi2026linear,
title = {{Linear arboricity conjecture for infinite graphs}},
author = {Leandro Aurichi and Rodrigo Santos Monteiro and Caio Fernando Rodrigues},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02065},
eprint = {2610.02065},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02065},
}
RIS
TY - UNPB
TI - Linear arboricity conjecture for infinite graphs
AU - Leandro Aurichi
AU - Rodrigo Santos Monteiro
AU - Caio Fernando Rodrigues
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.02065
UR - https://arxiv.org/abs/2610.02065
AB - The linear arboricity la(G) of a graph G is the least cardinality of linear forests, that is, forests of maximum degree at most $2$, into which its edge set E(G) can be decomposed. The Linear Arboricity Conjecture asserts that la(G)≤⌈(Δ(G)+1)/2⌉ for every finite graph G, where Δ(G) denotes the maximum degree of G. 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 latop (G) 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 2k-regular graph of girth at least 2k has topological linear arboricity at most k+1.
ER -