Trees, paths, stars, caterpillars and spiders
From MaRDI portal
Publication:1635718
DOI10.1007/s00453-016-0237-5zbMath1390.68322OpenAlexW2536897684MaRDI QIDQ1635718
Publication date: 1 June 2018
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-016-0237-5
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)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
- On star and caterpillar arboricity
- The linear arboricity of graphs
- NP-completeness of edge-colouring some restricted 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
- The subchromatic number of a graph
- Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
- Star arboricity of graphs
- Caterpillar arboricity of planar graphs
- Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
- A Planar linear arboricity conjecture
- The NP-Completeness of Edge-Coloring
- Complexité de l'arboricité linéaire d'un graphe
- Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
- Graph Subcolorings: Complexity and Algorithms
- NP completeness of finding the chromatic index of regular graphs
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- Decomposition of Finite Graphs Into Forests
- Linear arboricity and linear \(k\)-arboricity of regular graphs
This page was built for publication: Trees, paths, stars, caterpillars and spiders
