1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 10, 2016 at 19:09
  • $\begingroup$ Thanks for the links, Is it always possible for bounded degree graphs $\Delta=2d$ to find a colouring with an approximation ratio of $d$? $\endgroup$ Mar 11, 2016 at 17:39
  • $\begingroup$ 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$. $\endgroup$ Mar 14, 2016 at 20:58

1 Answer 1

4
$\begingroup$

According to graphclasses 3-Colourability of 4-regular ∩ planar is NP-hard. Check "+details" for reference.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.