The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones

DOI10.1016/J.IPL.2014.09.018zbMath1304.05045OpenAlexW2045373821MaRDI QIDQ477637

Krzysztof Turowski, Robert Janczewski

Publication date: 9 December 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2014.09.018

zbMATH Keywords

graph algorithmsbounded-degree graphsbackbone chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07)

Related Items (1)

On the hardness of computing span of subcubic graphs

Cites Work

• The backbone coloring problem for bipartite backbones
• \(\lambda \)-backbone colorings along pairwise disjoint stars and matchings
• Some simplified NP-complete graph problems
• Backbone colorings for graphs: Tree and path backbones
• Improved Upper Bounds for λ-Backbone Colorings Along Matchings and Stars
• Combinatorial Geometry and Graph Theory

This page was built for publication: The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones