Linear \(k\)-arboricities on trees

DOI10.1016/S0166-218X(99)00247-4zbMath0958.05069OpenAlexW2003295666MaRDI QIDQ1570841

Kuo-Ching Huang, Bor-Liang Chen, Hung-Lin Fu, Gerard Jennhwa Chang

Publication date: 9 April 2001

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00247-4

zbMATH Keywords

treeNP-completeleaflinear-time algorithmlinear forestlinear \(k\)-arboricity

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (17)

An improved upper bound on the linear 2-arboricity of 1-planar graphs ⋮ Linear 2-arboricity of planar graphs with neither 3-cycles nor adjacent 4-cycles ⋮ On the linear \((n - 1)\)-arboricity of \(K_{n(m)}\) ⋮ Edge-intersection graphs of boundary-generated paths in a grid ⋮ The linear 2-arboricity of IC-planar graphs ⋮ The linear 2-arboricity of sparse graphs ⋮ Linear 2-arboricity of toroidal graphs ⋮ The linear 3-arboricity of \(K_{n,n}\) and \(K_n\) ⋮ An improved upper bound on the linear 2-arboricity of planar graphs ⋮ The linear 2- and 4-arboricity of complete bipartite graph \(K_{m,n}\) ⋮ A note on the linear 2-arboricity of planar graphs ⋮ On the linear 2-arboricity of planar graph without normally adjacent 3-cycles and 4-cycles ⋮ Planar graphs without 5-cycles or without 6-cycles ⋮ Linear \(k\)-arboricity of Caylay graphs on abelian groups with given degree ⋮ Light structures in 1-planar graphs with an application to linear 2-arboricity ⋮ The linear \((n - 1)\)-arboricity of some lexicographic product graphs ⋮ The linear 2-arboricity of 1-planar graphs without 3-cycles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On linear k-arboricity
• The linear arboricity of graphs
• Some problems about linear arboricity
• The path-partition problem in bipartite distance-hereditary graphs
• Algorithmic aspects of linear \(k\)-arboricity
• La k-Arboricité Linéaire Des Arbres
• The linear arboricity of some regular graphs
• Linear arboricity of digraphs
• Some results on linear arboricity
• The NP-Completeness of Edge-Coloring
• Covering and packing in graphs IV: Linear arboricity
• Complexité de l'arboricité linéaire d'un graphe
• COVERING AND PACKING IN GRAPHS, I.

This page was built for publication: Linear \(k\)-arboricities on trees