On the hardness of computing span of subcubic graphs

DOI10.1016/j.ipl.2015.08.009zbMath1343.68097OpenAlexW2200934108MaRDI QIDQ888955

Robert Janczewski, Krzysztof Turowski

Publication date: 5 November 2015

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

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

zbMATH Keywords

computational complexityvertex coloringspansubcubic graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones
• Three short proofs in graph theory
• The complexity of satisfiability problems
• Combinatorial Geometry and Graph Theory

This page was built for publication: On the hardness of computing span of subcubic graphs