I'm fairly new to colourings on bounded degree graphs i'm interested in the following questions,
For planar graphs with bounded degree $4$ is finding the colouring number $NP$-hard? So is essentially deciding whether a graph is 3-colourable NP-complete?
For graphs $G$ with bounded degree $d$ i.e $\Delta(G)\leq d$, what is the best constant factor approximation we can obtain (assuming one exists) for the colouring number? Is there a proof that we cannot do any better than this bound in the worst case?
Links to papers containing any of the result will be much appreciated, thanks.