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.
