10
$\begingroup$

I heard of a result in approximate graph coloring, but cannot find the source. The result is:

For every constant $h$ there exists a sufficiently large $k$ such that coloring a $k$-colorable graph with $hk$ colors is NP-hard.

Could someone please point me to the relevant paper?

$\endgroup$
11
$\begingroup$

Here are the references:

$\endgroup$
11
$\begingroup$

There are much stronger results for approximate graph coloring.

$\endgroup$
  • $\begingroup$ The last result is interesting, but is there a decimal point mishap there? Two zeros before the decimal is odd... $\endgroup$ – Jeremy Kun Feb 21 '14 at 4:00

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.