Trees, Paths, Stars, Caterpillars and Spiders

摘要

For any $$k ge 2$$ k ≥ 2 , deciding whether the linear arboricity, star arboricity, caterpillar arboricity, spider arboricity, track number, unit track number, and subchromatic index, respectively, of a bipartite graph are at most k are all NP-complete.