The NP-completeness of (1,r)-subcolorability of cubic graphs

DOI10.1016/S0020-0190(01)00205-8zbMath1032.68122MaRDI QIDQ1603517

Van Bang Le, Hoàng-Oanh Le

Publication date: 14 July 2002

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

zbMATH Keywords

Computational complexityPlanar graphCombinatorial problemCubic graphSubcoloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (4)

Monopolar graphs: complexity of computing classical graph parameters ⋮ Complexity and algorithms for recognizing polar and monopolar graphs ⋮ Stable-\(\Pi\) partitions of graphs ⋮ The complexity of some acyclic improper colourings

Cites Work

• Unnamed Item
• Unnamed Item
• Some simplified NP-complete graph problems
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• The subchromatic number of a graph
• The complexity of satisfiability problems

This page was built for publication: The NP-completeness of (1,r)-subcolorability of cubic graphs