The NP-completeness of (1,r)-subcolorability of cubic graphs
type: Item
instance of: scholarly article
title: The NP-completeness of (1,r)-subcolorability of cubic graphs
zbMATH Open document ID: 1032.68122
DOI: 10.1016/S0020-0190(01)00205-8
author: Hoàng-Oanh Le
author: Van Bang Le
published in: Information Processing Letters
publication date: 2002-07-14T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1767421
zbMATH Keywords: Cubic graph
zbMATH Keywords: Planar graph
zbMATH Keywords: Subcoloring
zbMATH Keywords: Computational complexity
zbMATH Keywords: Combinatorial problem
MaRDI profile type: Publication
cites work: The subchromatic number of a graph
cites work: Q5588434
cites work: Q4198056
cites work: Some simplified NP-complete graph problems
cites work: On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
cites work: The complexity of satisfiability problems
Recommended article: NP-completeness of 4-incidence colorability of semi-cubic graphs
Recommended article: A concise proof for total coloring subcubic graphs
Recommended article: Total Colouring of New Classes of Subcubic graphs
Recommended article: Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs
Recommended article: Bounds and complexity results for strong edge colouring of subcubic graphs
Recommended article: Q4808623
Recommended article: COLORING ALGORITHMS ON SUBCUBIC GRAPHS
Recommended article: The complexity of some problems related to GRAPH 3-COLORABILITY
Recommended article: Q5866345
Recommended article: Acyclic colorings of subcubic graphs
description: scientific article; zbMATH DE number 1767421