Please use this identifier to cite or link to this item: https://idr.l1.nitk.ac.in/jspui/handle/123456789/15088
Title: The Linear Arboricity Conjecture for 3-Degenerate Graphs
Authors: Basavaraju M.
Bishnu A.
Francis M.
Pattanayak D.
Issue Date: 2020
Citation: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) , Vol. 12301 LNCS , , p. 376 - 387
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 χl′(G) 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, χl′(G)≤⌈Δ(G)+12⌉ where Δ(G) 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 ⌈Δ(G)+12⌉ linear forests. Since χl′(G)≥⌈Δ(G)2⌉ for any graph G, the partition produced by the algorithm differs in size from the optimum by at most an additive factor of 1. © 2020, Springer Nature Switzerland AG.
URI: https://doi.org/10.1007/978-3-030-60440-0_30
http://idr.nitk.ac.in/jspui/handle/123456789/15088
Appears in Collections:2. Conference Papers

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.