The list linear arboricity of graphs

DOI10.1002/JGT.22685MaRDI QIDQ6056776zbMATH OpenOpenAlexFDO

Authors Ringi Kim, Luke Postle

Publication date 4 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.05006

zbMATH Keywords

arboricitylinear arboricitylist coloring

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A linear forest is a forest in which every connected component is a path. The linear arboricity of a graph $G$ is the minimum number of linear forests of $G$ covering all edges. In 1980, Akiyama, Exoo and Harary proposed a conjecture, known as the Linear Arboricity Conjecture (LAC), stating that every $d$-regular graph $G$ has linear arboricity $lceilfracd+12ceil$. In 1988, Alon proved that the LAC holds asymptotically. In 1999, the list version of the LAC was raised by An and Wu, which is called the List Linear Arboricity Conjecture. In this article, we prove that the List Linear Arboricity Conjecture holds asymptotically.

Recommendations

• The list linear arboricity of planar graphs
• The linear arboricity of graphs
• scientific article; zbMATH DE number 4085704
• scientific article; zbMATH DE number 5846193
• List point arboricity of graphs
• scientific article; zbMATH DE number 140103
• Linear arboricity of digraphs
• scientific article; zbMATH DE number 966822
• The linear arboricity of some regular graphs
• Some results on total arboricity and list total arboricity of graphs

Cites work

• A note on list arboricity
• A note on vertex list colouring
• Asymptotically good list-colorings
• Concentration of measure and isoperimetric inequalities in product spaces
• Covering and packing in graphs IV: Linear arboricity
• COVERING AND PACKING IN GRAPHS, I.
• Decomposition of Finite Graphs Into Forests
• Graph colouring and the probabilistic method
• scientific article; zbMATH DE number 3989394 (Why is no real title available?)
• scientific article; zbMATH DE number 3717365 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 1299961 (Why is no real title available?)
• scientific article; zbMATH DE number 3353324 (Why is no real title available?)
• Some results on linear arboricity
• The linear arboricity of graphs
• The linear arboricity of planar graphs of maximum degree seven is four
• The linear arboricity of series-parallel graphs
• The linear arboricity of some regular graphs
• The list linear arboricity of planar graphs
• The probabilistic method

Cited in

(11)

• List point arboricity of dense graphs
• A note on list arboricity
• The linear arboricity of composition graphs
• Linear arboricity of regular digraphs
• scientific article; zbMATH DE number 5846193 (Why is no real title available?)
• The list linear arboricity of planar graphs
• Note on linear arboricity of graphs with large girth
• Almost Every Graph can be Covered by Linear Forests
• Rainbow subgraphs in Hamiltonian cycle decompositions of complete graphs
• An improved upper bound on the linear 2-arboricity of toroidal graphs
• Systematic generation of linear graphs - check and extension of the list of Uhlenbeck and Ford

This page was built for publication: The list linear arboricity of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6056776)