Trees, paths, stars, caterpillars and spiders
type: Item
instance of: scholarly article
title: Trees, paths, stars, caterpillars and spiders
zbMATH Open document ID: 1390.68322
published in: Algorithmica
publication date: 2018-06-01T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6879869
zbMATH Keywords: graph decomposition
zbMATH Keywords: arboricity
zbMATH Keywords: interval number
zbMATH Keywords: subcoloring
zbMATH Keywords: NP-hardness
author: Minghui Jiang
MaRDI profile type: Publication
full work available at URL: s00453-016-0237-5
OpenAlex ID: W2536897684
cites work: Q3907606
cites work: The subchromatic number of a graph
cites work: The linear arboricity of graphs
cites work: Linear arboricity and linear \(k\)-arboricity of regular graphs
cites work: NP-completeness of edge-colouring some restricted graphs
cites work: Q4313087
cites work: Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
cites work: A planar linear arboricity conjecture
cites work: Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
cites work: Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
cites work: Graph Subcolorings: Complexity and Algorithms
cites work: Q5445048
cites work: Forests, frames, and games: Algorithms for matroid sums and applications
cites work: Subcolorings and the subchromatic number of a graph
cites work: Caterpillar arboricity of planar graphs
cites work: On star and caterpillar arboricity
cites work: Star arboricity of graphs
cites work: The NP-Completeness of Edge-Coloring
cites work: Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
cites work: A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
cites work: NP completeness of finding the chromatic index of regular graphs
cites work: Q4083461
cites work: On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
cites work: Decomposition of Finite Graphs Into Forests
cites work: Complexité de l'arboricité linéaire d'un graphe
DOI: 10.1007/S00453-016-0237-5
description: scientific article; zbMATH DE number 6879869