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

<p>The treewidth of a planar graphs on $n$ vertices is $O(\sqrt{n})$
and 3-coloring it is $O(\exp{\sqrt{n}})$ as shown <a href="http://www.cs.bme.hu/~dmarx/papers/marx-faw-2013-planar.pdf" rel="nofollow noreferrer">here p. 8 of the pdf</a>.</p>

<p><a href="http://www.cs.cmu.edu/afs/cs/academic/class/15451-s04/www/Lectures/chapter23.pdf" rel="nofollow noreferrer">This paper</a> 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.</p>

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

<p>According to <a href="https://arxiv.org/abs/1012.0255" rel="nofollow noreferrer">second paper</a> for bounded
degree graphs, we get approximation with $O(n\log^4{n})$ crossings.</p>

<p>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.</p>

<blockquote>
  <p>Q1 Is this result correct?</p>
</blockquote>

<p>To our knowledge edge coloring 3-regular graph is exponential.</p>

CC BY-SA 4.0
2018-05-03T16:17:42.593Z
Cross-posted from https://mathoverflow.net/q/299320
Emil Jeřábek
CC BY-SA 4.0
2018-05-03T17:25:16.807Z
Degree 3 expander graphs need $\Omega(n^2)$ crossings (I think there was even a post here about it) so the last step is incorrect
daniello
CC BY-SA 4.0
2018-05-03T17:37:39.097Z
As I already commented on the MO question, the Chuzhoy paper is misquoted.
Emil Jeřábek
CC BY-SA 4.0
2018-05-03T18:33:22.543Z
Also, 3-coloring on bounded degree graphs in $2^{o(n)}$ time would violate the ETH.
daniello
CC BY-SA 4.0
2018-05-03T19:55:43.913Z
Simultaneous cross-posting to this site and mathoverflow is forbidden. This question should be closed because of this.
David Eppstein
CC BY-SA 4.0
2018-05-04T16:45:17.137Z
Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068). Each community should have an honest shot at answering without anybody's time being wasted.
D.W.
<cc.complexity-theory><graph-theory><graph-algorithms><planar-graphs><graph-colouring>
Is 3-coloring bounded degree graphs subexponential: $O(\exp{(\sqrt{n}\log^2{n})})$?
joro
# Is 3-coloring bounded degree graphs subexponential: $O(\exp{(\sqrt{n}\log^2{n})})$?

(Asked by: username_0 on 2018-05-03)

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}})$ as shown [here p. 8 of the pdf](http://www.cs.bme.hu/~dmarx/papers/marx-faw-2013-planar.pdf).

[This paper](http://www.cs.cmu.edu/afs/cs/academic/class/15451-s04/www/Lectures/chapter23.pdf) 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](https://arxiv.org/abs/1012.0255) 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.

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, planar-graphs, graph-colouring
> **Comments:**
> **username_1**: Cross-posted from https://mathoverflow.net/q/299320  
> **username_2**: Degree 3 expander graphs need $\Omega(n^2)$ crossings (I think there was even a post here about it) so the last step is incorrect  
> **username_1**: As I already commented on the MO question, the Chuzhoy paper is misquoted.  
> **username_2**: Also, 3-coloring on bounded degree graphs in $2^{o(n)}$ time would violate the ETH.  
> **username_3**: Simultaneous cross-posting to this site and mathoverflow is forbidden. This question should be closed because of this.  
> **username_4**: Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068). Each community should have an honest shot at answering without anybody's time being wasted.  

---

## 0 answers

