Trees, Paths, Stars, Caterpillars and Spiders

DOI10.1007/978-3-319-26626-8_40zbMath1386.68064OpenAlexW2396543733MaRDI QIDQ3467870

Ming-Hui Jiang

Publication date: 5 February 2016

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-26626-8_40

zbMATH Keywords

NP-hardnessarboricityedge partition

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• On star and caterpillar arboricity
• The linear arboricity of graphs
• Forests, frames, and games: Algorithms for matroid sums and applications
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• Subcolorings and the subchromatic number of a graph
• Star arboricity of graphs
• Caterpillar arboricity of planar graphs
• Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
• A Planar linear arboricity conjecture
• Complexité de l'arboricité linéaire d'un graphe
• Graph Subcolorings: Complexity and Algorithms
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• Decomposition of Finite Graphs Into Forests