3-coloring planar graphs in $O\left(3^{n^.5}\right)$?

Question

I was wondering if the task of searching for planar 3-colorings is known to be of complexity $O\left(c^{\sqrt{n}}\right)$ or lower? This feels like it would be an intuitive consequence based from planar separator results, yet in wikipedia, it only mentions independent sets, Steiner trees, Hamiltonian cycles, and TSP. Below I include some reasoning which I think almost does achieve this bound.

With a zero reduced decision diagram, (ZDD), I believe you can get $O\left(c^{O(log_2(n)\sqrt{n})}\right)$, and I was curious how I could do better. What I came up with is rather rudimentary. Note: throughout, the ZDD I describe is ternary, but I don’t think that greatly matters. For the ZDD, given an ordering, $L = \{v_1 \dots v_n\}$, of vertices to color, the number of nodes at step $i$ will be exponential in respect to the size the frontier, $F_i = \{v_k | k < i \land v_k~v_j, j \geq i \}$.

To create your ordering $L$, you may create an optimal branch-decomposition tree, $b$, in polynomial time, which has width at most $\sqrt{n}$. Then, select a random leaf $v’$ of $b$ to be your root. With a BFS, weight each edge $e$ by the number of leaves not connected to $v’$ if you were to remove $e$ from $b$. Then, do a DFS to finally create $L$, always going down the edge furtherest from $v’$, choosing the one with least weight if there is a tie, and choosing arbitrarily if there is still a tie. When we reach a leaf, $(u,v)$ add $u$/$v$ to $L$ if either is not in $L$. Let $c_i$ be the component induced in $b$ by the vertices visited when we added $v_i$ to $L$. Then, $F_i$ is bounded by the branch width times the number of edges $x_i$ needs to be removed from $b$ to get the component $c_i$. $x$ is bounded roughly by $log_2$ of the vertices in $b$, which is linear to $n$ since we’re dealing with planar graphs.

With that, you check all three colors for each node for each of the $n$ frontiers and you’re done.

Answer 1

I recommend reading Sections 7 and 14 in the excellent book by Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, and Saurabh.

In short, Gu and Tamaki give a quadratic time algorithm which finds a branch-decomposition of a planar graph of width at most $3\sqrt{n}$. Then Robertson and Seymour in (5.1) give a tree-decomposition of width less than $\frac{9\sqrt{n}}{2}$. Then the classical dynamic programming algorithm (see, e.g., Marx) solves $3$-Coloring in time $3^{\frac{9\sqrt{n}}{2}}\textrm{poly}(n)<141^{\sqrt{n}}$.

On the other hand, it is known (Lichtenstein) that under the Exponential Time Hypothesis (ETH), the Planar $3$-SAT problem is $2^{\Omega(\sqrt{n})}$-hard. And a reduction from Planar $3$-SAT to Planar $3$-Coloring implies that under ETH there is no algorithm solving Planar $3$-Coloring in time $2^{o(\sqrt{n})}$.