The Linear Arboricity Conjecture for Graphs with Large Girth
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908707155083264 |
|---|---|
| author | Mishra, Tapas Kumar |
| author_facet | Mishra, Tapas Kumar |
| contents | The Linear Arboricity Conjecture asserts that the linear arboricity of a graph with maximum degree $Δ$ is $\lceil (Δ+1)/2 \rceil$. For a $2k$-regular graph $G$, this implies $la(G) = k+1$. In this note, we utilize a network flow construction to establish upper bounds on $la(G)$ conditioned on the girth $g(G)$. We prove that if $g(G) \ge 2k$, the conjecture holds true, i.e., $la(G) \le k+1$. Furthermore, we demonstrate that for graphs with girth $g(G)$ at least $k$, $k/2$, $k/4$ and $2k/c$ for any integer constant $c$, the linear arboricity $la(G)$ satisfies the upper bounds $k+2$, $k+3$, $k+5$ and $k+\left\lceil \frac{3c+2}{2}\right\rceil$, respectively. Our approach relies on decomposing the graph into $k$ edge-disjoint 2-factors and constructing an auxiliary flow network with lower bound constraints to identify a sparse transversal subgraph that intersects every cycle in the decomposition. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_11240 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Linear Arboricity Conjecture for Graphs with Large Girth Mishra, Tapas Kumar Combinatorics Discrete Mathematics 05C70, 05C21 The Linear Arboricity Conjecture asserts that the linear arboricity of a graph with maximum degree $Δ$ is $\lceil (Δ+1)/2 \rceil$. For a $2k$-regular graph $G$, this implies $la(G) = k+1$. In this note, we utilize a network flow construction to establish upper bounds on $la(G)$ conditioned on the girth $g(G)$. We prove that if $g(G) \ge 2k$, the conjecture holds true, i.e., $la(G) \le k+1$. Furthermore, we demonstrate that for graphs with girth $g(G)$ at least $k$, $k/2$, $k/4$ and $2k/c$ for any integer constant $c$, the linear arboricity $la(G)$ satisfies the upper bounds $k+2$, $k+3$, $k+5$ and $k+\left\lceil \frac{3c+2}{2}\right\rceil$, respectively. Our approach relies on decomposing the graph into $k$ edge-disjoint 2-factors and constructing an auxiliary flow network with lower bound constraints to identify a sparse transversal subgraph that intersects every cycle in the decomposition. |
| title | The Linear Arboricity Conjecture for Graphs with Large Girth |
| topic | Combinatorics Discrete Mathematics 05C70, 05C21 |
| url | https://arxiv.org/abs/2512.11240 |