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.

Improve this question
$\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$
    – Florent Foucaud
    Commented 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$
    – Pavan Sangha
    Commented 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$
    – Florent Foucaud
    Commented Mar 14, 2016 at 20:58

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .