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 \(\chi _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, \(\chi _l'(G)\le \left\lceil \frac{\varDelta (G)+1}{2}\right\rceil \) where \(\varDelta (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 \(\left\lceil \frac{\varDelta (G)+1}{2}\right\rceil \) linear forests. Since \(\chi '_l(G)\ge \left\lceil \frac{\varDelta (G)}{2}\right\rceil \) for any graph G, the partition produced by the algorithm differs in size from the optimum by at most an additive factor of 1.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Akiyama, J., Exoo, G., Harary, F.: Covering and packing in graphs III: cyclic and acyclic invariants. Math. Slovaca 30(4), 405–417 (1980)
Akiyama, J., Exoo, G., Harary, F.: Covering and packing in graphs IV: linear arboricity. Networks 11, 69–72 (2006)
Alon, N.: The linear arboricity of graphs. Israel J. Math. 62(3), 311–325 (1988). https://doi.org/10.1007/BF02783300
Alon, N., Spencer, J.H.: The Probabilistic Method, 4th edn. Wiley, Hoboken (2016)
Basavaraju, M., Bishnu, A., Francis, M., Pattanayak, D.: The linear arboricity conjecture for 3-degenerate graphs. arXiv:2007.06066 (2020)
Basavaraju, M., Chandran, L.S.: Acyclic edge coloring of 2-degenerate graphs. J. Graph Theory 69(1), 1–27 (2012)
Cygan, M., Hou, J.-F., Kowalik, Ł., Lužar, B., Jian-Liang, W.: A planar linear arboricity conjecture. J. Graph Theory 69(4), 403–425 (2012)
Diestel, R.: Graph Theory. GTM, vol. 173. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-53622-3
Enomoto, H., Peroche, B.: The linear arboricity of some regular graphs. J. Graph Theory 8(2), 309–324 (1984)
Ferber, A., Fox, J., Jain, V.: Towards the linear arboricity conjecture. J. Comb. Theory Ser. B 142, 56–79 (2019)
Gabow, H., Westermann, H.: Forests, frames, and games: algorithms for matroid sums and applications. Algorithmica 7(5–6), 465–497 (1992). https://doi.org/10.1007/BF01758774
Guldan, F.: The linear arboricity of 10-regular graphs. Math. Slovaca 36(3), 225–228 (1986)
Guldan, F.: Some results on linear arboricity. J. Graph Theory 10(4), 505–509 (1986)
Harary, F.: Covering and packing in graphs, I. Ann. New York Acad. Sci. 175(1), 198–205 (1970)
Hsiao, D., Harary, F.: A formal system for information retrieval from files. Commun. ACM 13(2), 67–73 (1970)
Peroche, B.: Complexité de l’arboricité linéaire d’un graphe. RAIRO-Oper. Res. 16(2), 125–129 (1982)
Vizing, V.G.: On an estimate of the chromatic class of a \(p\)-graph. Diskret. Analiz 3, 25–30 (1964)
Jian-Liang, W.: On the linear arboricity of planar graphs. J. Graph Theory 31(2), 129–134 (1999)
Jian-Liang, W., Yu-Wen, W.: The linear arboricity of planar graphs of maximum degree seven is four. J. Graph Theory 58(3), 210–220 (2008)
Acknowledgements
The first author was partially supported by the fixed grant scheme SERB-MATRICS project number MTR/2019/000790.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Basavaraju, M., Bishnu, A., Francis, M., Pattanayak, D. (2020). The Linear Arboricity Conjecture for 3-Degenerate Graphs. In: Adler, I., Müller, H. (eds) Graph-Theoretic Concepts in Computer Science. WG 2020. Lecture Notes in Computer Science(), vol 12301. Springer, Cham. https://doi.org/10.1007/978-3-030-60440-0_30
Download citation
DOI: https://doi.org/10.1007/978-3-030-60440-0_30
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-60439-4
Online ISBN: 978-3-030-60440-0
eBook Packages: Computer ScienceComputer Science (R0)