On star and caterpillar arboricity

DOI10.1016/j.disc.2008.01.041zbMath1228.05127OpenAlexW1973171062WikidataQ56428506 ScholiaQ56428506MaRDI QIDQ1025569

Pascal Ochem, Daniel Gonçalves

Publication date: 19 June 2009

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

Full work available at URL: https://doi.org/10.1016/j.disc.2008.01.041

zbMATH Keywords

edge coloringNP-completenesspartitioning problems

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

Trees, paths, stars, caterpillars and spiders ⋮ Trees, Paths, Stars, Caterpillars and Spiders ⋮ 2-subcoloring is NP-complete for planar comparability graphs ⋮ Two dependency constrained spanning tree problems ⋮ Three ways to cover a graph ⋮ Local and union boxicity ⋮ Edge-intersection graphs of grid paths: the bend-number ⋮ The interval number of a planar graph is at most three ⋮ On the bend-number of planar and outerplanar graphs ⋮ Planar projections of graphs ⋮ On interval representations of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• More about subcolorings
• The interval number of a planar graph: Three intervals suffice
• Some simplified NP-complete graph problems
• On the maximum average degree and the oriented chromatic number of a graph
• Subcolorings and the subchromatic number of a graph
• Star arboricity of graphs
• Caterpillar arboricity of planar graphs
• Acyclic Colourings of Planar Graphs with Large Girth
• The NP-Completeness of Edge-Coloring
• Graph Classes: A Survey
• Graph Subcolorings: Complexity and Algorithms
• Decomposition of Finite Graphs Into Forests