1. D4G3C

We'll show that it is NP-complete by reduction from GRAPH 3-COLORABILITY. The key idea is that we have to replace each vertex v with too many neighbors with a graph G_v with "external" vertices v₁, v₂, v₃, etc. such that (a) every vertex in G_v has degree 4 or less, (b) every vertex v_i has degree 3 or less, and (c) in any coloring the v_i all have the same color. Here's the basic construction in glorious ASCII art (the R nodes are the external ones):

  R
 / \
G---B
|\ /|
| X |
|/ \|
R   R

Note that since the external nodes all have degree 2, we can paste multiple copies of this widget together to get more external nodes without violating the degree bound:

  R
 / \
G---B
|\ /|
| X |
|/ \|
R   R
   / \
  G---B
  |\ /|
  | X |
  |/ \|
  R   R

and by repeating this expansion we can add as many degree-2 external nodes as we like. So given a degree-k node in the original graph, we replace it with a stack of widgets with ⌈k/2⌉ external nodes and run each edge that used to go to the degree-k node to one of the external nodes (with at most two edges per node). Any coloring of the original graph translates into a coloring of the constructed graph by coloring the external nodes of each stack of widgets the same as the original node (and coloring internal nodes appropriately); conversely, a coloring of the constructed graph translates into a coloring of the original graph by collapsing all the widgets back into single nodes. Since we can easily construct all the needed widgets in polynomial time, this shows GRAPH 3-COLORABILITY is poly-time reducible to DEGREE 4 GRAPH 3-COLORABILITY, and so D4G3C is NP-hard. To show that it is in NP, observe that D4G3C reduces to G3C using the O(0) time identity function.

2. D4G2C

D4G2C is actually pretty easy; it's a special case of GRAPH 2-COLORABILITY, which is also easy. A 2-coloring of a graph is a partition of the nodes into sets A and B such that for every edge one endpoint is in A and one endpoint is in B. Any solution (A,B) can be reversed (B,A) by renaming the sets, so if we pick some particular starting vertex x, we can put it in A with no loss of generality. But then every neighbor of x must be in B, their neighbors must be in A, and so forth.

So an algorithm to test for 2-colorability is to run DFS, coloring every vertex at an even depth A and every vertex at an odd depth B. Then the graph is 2-colorable if and only if there is no non-tree edge between an A vertex and a B vertex, which we can test in linear time.