The linear arboricity conjecture for 3-degenerate graphs
M Basavaraju, A Bishnu, M Francis… - Graph-Theoretic Concepts …, 2020 - Springer
M Basavaraju, A Bishnu, M Francis, D Pattanayak
Graph-Theoretic Concepts in Computer Science: 46th International Workshop, WG …, 2020•SpringerA k-linear coloring of a graph G is an edge coloring of G with k colors so that each color
class forms a linear forest—a forest whose each connected component is a path. The linear
arboricity χ _l'(G) χ l′(G) of G is the minimum integer k such that there exists ak-linear
coloring of G. Akiyama, Exoo and Harary conjectured in 1980 that for every graph G, χ _l'(G)
≤\left ⌈\varDelta (G)+ 1 2\right ⌉ χ l′(G)≤ Δ (G)+ 1 2 where\varDelta (G) Δ (G) is the
maximum degree of G. We prove the conjecture for 3-degenerate graphs. This establishes …
class forms a linear forest—a forest whose each connected component is a path. The linear
arboricity χ _l'(G) χ l′(G) of G is the minimum integer k such that there exists ak-linear
coloring of G. Akiyama, Exoo and Harary conjectured in 1980 that for every graph G, χ _l'(G)
≤\left ⌈\varDelta (G)+ 1 2\right ⌉ χ l′(G)≤ Δ (G)+ 1 2 where\varDelta (G) Δ (G) is the
maximum degree of G. We prove the conjecture for 3-degenerate graphs. This establishes …
Abstract
A k-linear coloring of a graph G is an edge coloring of G with k colors so that each color class forms a linear forest—a forest whose each connected component is a path. The linear arboricity of G is the minimum integer k such that there exists a k-linear coloring of G. Akiyama, Exoo and Harary conjectured in 1980 that for every graph G, where is the maximum degree of G. We prove the conjecture for 3-degenerate graphs. This establishes the conjecture for graphs of treewidth at most 3 and provides an alternative proof for the conjecture for triangle-free planar graphs. Our proof also yields an O(n)-time algorithm that partitions the edge set of any 3-degenerate graph G on n vertices into at most linear forests. Since for any graph G, the partition produced by the algorithm differs in size from the optimum by at most an additive factor of 1.
Springer