Please use this identifier to cite or link to this item: https://idr.l3.nitk.ac.in/jspui/handle/123456789/15088
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBasavaraju M.
dc.contributor.authorBishnu A.
dc.contributor.authorFrancis M.
dc.contributor.authorPattanayak D.
dc.date.accessioned2021-05-05T10:16:24Z-
dc.date.available2021-05-05T10:16:24Z-
dc.date.issued2020
dc.identifier.citationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) , Vol. 12301 LNCS , , p. 376 - 387en_US
dc.identifier.urihttps://doi.org/10.1007/978-3-030-60440-0_30
dc.identifier.urihttp://idr.nitk.ac.in/jspui/handle/123456789/15088-
dc.description.abstractA 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.en_US
dc.titleThe Linear Arboricity Conjecture for 3-Degenerate Graphsen_US
dc.typeConference Paperen_US
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.