2025/12/12 by Mishra, Tapas Kumar
Computer Science · Mathematics · #05C21 #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems
paper · doi:10.48550/arxiv.2512.11240
openalex publication_date 2025/12/12 · openalex created_date 2025/12/16 · openalex updated_date 2026/07/28
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) ≥ 2k, the conjecture holds true, i.e., la(G) ≤ 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+\lceil (3c+2)/(2)\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.