# Graph colouring for bounded degree graphs

I'm fairly new to colourings on bounded degree graphs i'm interested in the following questions,

1. 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?

2. 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.

• It seems that the discussion on this page (cstheory.stackexchange.com/q/16817/1930) contains the state of the art (from three years ago) for your 2nd question. – Florent Foucaud Mar 10 '16 at 19:09
• Thanks for the links, Is it always possible for bounded degree graphs $\Delta=2d$ to find a colouring with an approximation ratio of $d$? – Pavan Sangha Mar 11 '16 at 17:39
• I think this is easily possible. First, you can check if your graph is bipartite, if yes, this gives you the optimal 2-colouring in polynomial time. Otherwise, the chromatic number is at least 3. You can easily construct a $(\Delta+1)$-colouring in polynomial time using an arbitrary ordering of your vertices and a greedy colouring algorithm. Thus this is a $(\Delta+1)/3$-approximation algorithm, in your case of $\Delta=2d$ that's a ratio of at most $(2d+1)/3$. – Florent Foucaud Mar 14 '16 at 20:58