Consider the set of graphs in which the maximum degree of the vertices is a constant number $\Delta$ independent of the number of vertices. Is the vertex coloring problem (that is, color the vertices with minimum number of colors such that no pair of adjacent nodes have the same color) on this set still NP-hard? Why?
Vertex coloring with an upper bound on the degree of the nodes
algorithms;complexity theory;graph theory;graphs;np complete
Yes, it's still NP-hard. 3-COL is still NP-complete for planar degree 4 graphs [1].Dailey, D. P. (1980), Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete, Discrete Mathematics 30 (3): 289293, DOI:10.1016/0012-365X(80)90236-8