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.

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.


closed as off-topic by David Eppstein, Jan Johannsen, Emil Jeřábek, D.W., Peter Shor May 6 '18 at 15:42

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Our site policy prohibits simultaneous crossposting: it duplicates effort and fractures discussion. Crossposting is permitted after a week has passed without a satisfying answer elsewhere. When crossposting please summarize the relevant discussions from other sites in your question and link between the copies in both directions." – David Eppstein, Jan Johannsen, Emil Jeřábek, D.W., Peter Shor
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Cross-posted from mathoverflow.net/q/299320 $\endgroup$ – Emil Jeřábek May 3 '18 at 16:17
  • 3
    $\begingroup$ 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 $\endgroup$ – daniello May 3 '18 at 17:25
  • 1
    $\begingroup$ As I already commented on the MO question, the Chuzhoy paper is misquoted. $\endgroup$ – Emil Jeřábek May 3 '18 at 17:37
  • 1
    $\begingroup$ Also, 3-coloring on bounded degree graphs in $2^{o(n)}$ time would violate the ETH. $\endgroup$ – daniello May 3 '18 at 18:33
  • 1
    $\begingroup$ Simultaneous cross-posting to this site and mathoverflow is forbidden. This question should be closed because of this. $\endgroup$ – David Eppstein May 3 '18 at 19:55