0
$\begingroup$

We got an argument that 3-coloring bounded degree graphs is subexponential with complexity $O(\exp{(\sqrt{n}\log^2{n})})$.

The treewidth of a planar graphs on $n$ vertices is $O(\sqrt{n})$ and 3-coloring it is $O(\exp{\sqrt{n}})$.

This paper gives reduction from 3-coloring to 3-coloring planar graph and the main idea is replace each edge crossing with a small gadget, which preserves colorability.

If for a bounded degree graph we can find drawing with $o(n^2)$ crossings, we get subexponential algorithm for 3-coloring it.

According to second paper for bounded degree graphs, we get approximation with $O(n\log^4{n})$ crossings.

After we have found drawing with few crossings, we planarize using the gadget. The resulting graph is bounded degree and planar and on $n+ C n\log^4{n}$ vertices.

Q1 Is this result correct?

To our knowledge edge coloring 3-regular graph is exponential.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Cross-posted to cstheory.stackexchange.com/q/40723 $\endgroup$
    – Emil Jeřábek
    Commented May 3, 2018 at 16:17
  • $\begingroup$ “$O(n\log^4n)$-approximation” does not mean a drawing with $O(n\log^4n)$ crossings, but a drawing whose number of crossings is at most $O(n\log^4n)$-times higher than in the optimal drawing. (Also, this is not what the paper proves, but an old result on which it improves.) $\endgroup$
    – Emil Jeřábek
    Commented May 3, 2018 at 16:32
  • $\begingroup$ Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$
    – D.W.
    Commented May 4, 2018 at 16:45

0

Reset to default

You must log in to answer this question.