pipette
ENEnglish

Linear arboricity conjecture for infinite graphs

Leandro Aurichi, Rodrigo Santos Monteiro, Caio Fernando Rodrigues

Preprint

En palabras de los autores

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 .

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 2 de octubre. arXiv. Preprint, todavía sin revisión por pares.