1
$\begingroup$

I was wondering if anyone could provide references on the following:

  1. Is determining the chromatic number of a bounded degree graph APX-complete?

2.I've seen the result that states it is NP-hard to decided whether a $4$ bounded graph is $3$ colourable. In general for a $d$ bounded degree graph which positive integers $k$ is it NP-hard to determine whether the graph is $k$-colourable?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ You can artificially increase the degree by adding a bipartite star graph. $\endgroup$
    – joro
    Commented May 10, 2016 at 12:04
  • $\begingroup$ Could you elaborate slightly? Are you saying for a fixed bounded degree $d$ we can prove hardness for all $k \leq d$ by making some sort of reduction which adds a bipartite star graph? If so where is the starting point of hardness $k=3$? $\endgroup$
    – Pavan Sangha
    Commented May 17, 2016 at 22:30
  • $\begingroup$ The starting point for $k=3$ is $d=4$ -- the line graph of 3-regular graph for which edge coloring is NP-hard. To get $d=5$ add new vertex and an edge to any of the vertices, this doesn't change the chromatic number. $\endgroup$
    – joro
    Commented May 18, 2016 at 6:12
  • $\begingroup$ yes i see this, how can we increase $k$ though? Maybe add a clique instead? $\endgroup$
    – Pavan Sangha
    Commented May 20, 2016 at 11:17

0

Reset to default

You must log in to answer this question.