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.

  • 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$ – Florent Foucaud Mar 10 '16 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$ – Pavan Sangha Mar 11 '16 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$ – Florent Foucaud Mar 14 '16 at 20:58

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.