#  3-colorability of graphs with minimum degree at least 6

Nicholas Crawford11footnotemark: 1 and Sogol Jahanbekam222 Department of
Mathematics and Statistics, San Jose State University, San Jose, CA;
<EMAIL_ADDRESS>
Research was supported in part by by NSF grant CMMI-1727743.

###### Abstract

Let $G$ be an $n$-vertex graph and let $L:V(G)\rightarrow P(\\{1,2,3\\})$ be a
list assignment over the vertices of $G$, where each vertex with list of size
3 and of degree at most 5 has at least three neighbors with lists of size 2.
We can determine $L$-choosability of $G$ in $O(1.3196^{n_{3}+.5n_{2}})$ time,
where $n_{i}$ is the number of vertices in $G$ with list of size $i$ for
$i\in\\{2,3\\}$. As a corollary, we conclude that the 3-colorability of any
graph $G$ with minimum degree at least 6 can be determined in
$O(1.3196^{n-.5\Delta(G)})$ time.

Keywords: algorithms, complexity, proper coloring, 68W01, 68Q25, 05C15

22footnotetext:  Department of Mathematics and Statistics, San Jose State
University, San Jose, CA<EMAIL_ADDRESS>.

##  1 Introduction

Let $G$ be a graph. We denote the vertex set of $G$ by $V(G)$, the edge set of
$G$ by $E(G)$, and the minimum degree of $G$ as $\delta(G)$. For a vertex $v$
in $G$, the open neighborhood of $v$ in $G$, denoted by $N(v)$, is the set of
neighbors of $v$ in $G$.

We say that a coloring of vertices of $G$ is _proper_ if all adjacent vertices
receive different colors. A graph $G$ is _k-colorable_ if it has a proper
coloring using at most _k_ colors. The _chromatic number_ of a graph G,
denoted $\chi(G)$, is the smallest integer _k_ such that G is _k_ -colorable.

Suppose for each vertex _v_ in $V(G)$, there exist a list of colors denoted
$L(v)$. A _proper list coloring_ of G is a choice function that maps every
vertex _v_ to a color in $L(v)$ in such a way that the coloring is proper. A
graph is $k$-choosable if it has a proper list coloring whenever each vertex
has a list of size $k$. For additional definitions we refer the reader to [7].

By the definition, a graph $G$ is 1-colorable if and only if it has no edge.
We can also apply a simple Breadth First Search algorithm to determine
2-coloability of a graph in polynomial time [7]. The $k$-colorability problem
for $k\geq 3$ is an NP-complete problem [5], and as a result determining the
chromatic number of a graph is NP-complete.

In 1971 Christofides discovered the first non-trivial algorithm for computing
the chormatic number of an $n$-vertex graph with complexity $n!n^{O(1)}$ [3].
The best known result for determining the chromatic number of a graph was done
by Björklund, Husfeldt, and Koivisto in 2009 with complexity $2^{n}O(1)$ [2].

The $k$-coloring problem is a highly studied problem in graph theory.
Improving the complexity for $k$-coloring problem, even for small values of
$k$ like 3 and 4, could lead to improved complexity of the general chromatic
number problem. In 2013, Eppstein and Beigal [1] created an algorithm that
determined whether a graph was 3-colorable in $O(1.3289^{n})$ time. This
algorithm is the lowest complexity algorithm to date for 3-colorability of
general graphs. Crawford et. al. proved in [4] that you can determine the 3
colorability of a graph with minimum degree at least 7 and 8 in
$O(1.32^{n-.73\Delta(G)})$ and $O(1.3158^{n-.7\Delta(G)})$, respectively.

In this paper, we prove the following results.

######  Theorem 1.

Let $G$ be an $n$-vertex graph with minimum degree at least 6. Let
$L:V(G)\rightarrow P{\\{1,2,3\\}}$ be a list assignment over the vertices of
$G$. We can determine $L$-choosability of $G$ in $O(1.3196^{n_{3}+.5n_{2}})$
time, where $n_{i}$ is the number of vertices in $G$ with list of size $i$ for
$i\in\\{2,3\\}$.

Note that if a vertex in a proper coloring of a graph $G$ using three colors
$1,2,3$ gets color 1, then each of its neighbors must get a color in
$\\{2,3\\}$. This observation and Theorem 1 imply the following corollary.

######  Corollary 2.

Let $G$ be an $n$-vertex graph with minimum degree at least $6$. We determine
in $O(1.3196^{n-.5\Delta(G)})$ time if $G$ is 3-colorable.

To prove Theorem 1 we prove the following stronger theorem.

######  Theorem 3.

Let $G$ be an $n$-vertex graph and let $L:V(G)\rightarrow P(\\{1,2,3\\})$ be a
list assignment over the vertices of $G$. If each vertex of degree at most 5
in $G$, with a list of size 3, has at least three neighbors with lists of size
2, then we can determine $L$-choosability of $G$ in
$O(1.3196^{n_{3}+.5n_{2}})$ time, where $n_{i}$ is the number of vertices with
list of size $i$ in $G$.

##  2 Proof of Theorem 3

We apply induction on $k$, the number of vertices of the graph, to prove that
if $L:V(G)\rightarrow P(\\{1,2,3\\})$ is a list assignment over the vertices
of a $k$-vertex graph $G$ with the condition that each vertex of degree at
most 5 in $G$, with a list of size 3, has at least three neighbors with lists
of size 2, then we can determine $L$-choosability of $G$ in
$O(1.3196^{k_{3}+.5k_{2}})$ time, where $k_{i}$ is the number of vertices in
$G$ with lists of size $i$.

If $k=1$, then $G=K_{1}$, which is $L$-choosable. Therefore in this case we
need no operation to determine $L$-choosability of $G$, where $L$ gives at
least 1 and at most 3 colors from $\\{1,2,3\\}$ to each vertex.

Now suppose the assertion holds for any graph satisfying the condition of the
problem and having smaller than $n$ vertices. Let $G$ be an $n$-vertex graph.
Suppose
$L:V(G)\rightarrow P(\\{1,2,3\\})$ is a list assignment over the vertices of
$G$ in such a way that each vertex of degree at most 5, and list of size 3,
has at least 3 neighbors with lists of size 2.

If $G$ has a vertex $u$ with a list of size 1, then we can remove the color in
$L(u)$ from the list of colors in the neighborhood of $u$ and then study the
smaller graph $G-u$. Hence we may suppose $G$ has no vertex with a list of
size 1. Suppose $G$ has $n_{3}$ vertices with lists of size 3 and $n_{2}$
vertices with lists of size 2.

We consider four cases. Note that each of the cases below is considering a
specific structure in graph $G$, which can be found via a polynomial-time
algorithm.

Case 1: A vertex $v$ with list size $3$ in $G$ is adjacent to at least 6
vertices with list size 3 (Figure 1).

Figure 1: Graph $G$ with List $L$.

There are three possibilities for the color of $v$: 1, 2, or 3. First suppose
$v$ gets color 1 in $G$. In this case remove color 1 from the lists on the
neighbors of $v$ and let $L^{\prime}$ be the resulting list assignment (Figure
2). In this case $G$ is $L$-choosable with vertex $v$ getting color 1 if and
only if $G-v$ is $L^{\prime}$-choosable.

Figure 2: When vertex $v$ gets color 1.

Note that at least 6 vertices in the neighborhood of $v$ have lists of size 3
in $L$ but lists of size 2 in $L^{\prime}$, because we have removed color 1
from their lists. Moreover, $v$ has a list of size 3 in $G$, while it is not a
vertex in $G-v$. Therefore $G-v$ contains at most $n_{3}-7$ vertices with
lists of size 3. Since $G-v$ has $n-1$ vertices, by the induction hypothesis
we can determine in $O((1.3196)^{n_{3}-7+.5(n_{2}+6)})$ time if it is
$L^{\prime}$-choosable.

A similar argument as above applies when $v$ gets color 2 or color 3. Hence we
can determine in $O(3(1.3196)^{n_{3}-7+.5(n_{2}+6)})$ time if $G$ is
$L$-choosable. Since
$3(1.3196)^{n_{3}-7+.5(n_{2}+6)}<(1.3196)^{n_{3}+.5n_{2}}$, the assertion
holds in this case.

Case 2: A vertex $v$ with list size 3 is adjacent to $5$ vertices with lists
of size 3.

By Case 1 and by the structure of $G$ we may suppose that $v$ has at least one
neighbor with list of size 2. Let $u_{1},\ldots,u_{5}$ be neighbors of $v$
with lists of size 3 and let $u_{6}$ be a neighbor of $v$ with list of size 2.
By symmetry we may suppose $L(u_{6})=\\{1,2\\}$. We consider three subcases.

First suppose $u_{6}$ has another neighbor $w$ with a list containing 2 (i.e.
$L(w)=\\{1,2\\}$, or $L(w)=\\{2,3\\}$, or $L(w)=\\{1,2,3\\}$). Note that the
vertex $v$ can get color 1, 2, or 3. If $v$ gets color 1 in $G$, then the
neighbors of $v$ cannot be color 1. Define $L^{\prime}(u)=L(u)-\\{1\\}$ for
all neighbors $u$ of $v$. Hence $L(u_{6})=\\{2\\}$. Therefore $u_{6}$ has to
get color 2 in this case. As a result, $w$ cannot receive color $2$ anymore.
Hence let $L^{\prime}(w)=L(w)-\\{2\\}$. Thus $G$ is $L$-choosable with $v$
getting color $1$ if and only if $G-\\{v,u_{6}\\}$ is $L^{\prime}$-choosable.
Note that $G-\\{v,u_{6}\\}$ has $n-2$ vertices. Moreover, it contains either
$n_{3}-7$ and $n_{2}+4$ vertices with lists of size 3 and 2, respectively, or
it contains $n_{3}-6$ and $n_{2}+3$ vertices with lists of size 3 and 2,
respectively (depending on the list size on vertex $w$).

We can repeat this argument for the case $v$ gets color 2 and 3. If $v$ gets
color $2$, then we can reduce the problem into $L^{\prime}$-choosability of
the graph $G-\\{v,u_{6}\\}$ with $n-2$ vertices, $n_{3}-6-i$ vertices with
lists of size 3 and $n_{2}+5-j$ vertices with lists of size 2, where
$\\{i,j\\}=\\{0,1\\}$. And when $v$ gets color $3$, then we can reduce the
problem into $L^{\prime}$-choosability of the graph $G-\\{v\\}$ with $n-1$
vertices, $n_{3}-6$ vertices with lists of size 3 and $n_{2}+5$ vertices with
lists of size 2. Hence we can determine in
$O((1.3196)^{n_{3}-6+.5(n_{2}+3)}+(1.3196)^{n_{3}-6+.5(n_{2}+4)}+(1.3196)^{n_{3}-6+.5(n_{2}+5)})$
time if $G$ is $L$-choosable. Since
$(1.3196)^{-6+.5(3)}+(1.3196)^{-6+.5(4)}+(1.3196)^{-6+.5(5)}\leq 1$, the
assertion holds in this case.

If $u_{6}$ has another neighbor $w$ with a list containing 1, we can repeat
the above argument by switching the arguments for the case $v$ gets colors 1
and 2 to get the desired conclusion. Hence the final subcase is when $u_{6}$
has no other neighbor containing color $1$ or $2$. This implies that $u_{6}$
has degree 1 in $G$. As a result, $L$-choosability of $G$ can be reduced to
list choosability of $G-\\{v,u_{6}\\}$, for three different list assignment
corresponding to the cases that $v$ gets color 1, 2, or 3. At each of these
cases, $G-\\{v,u_{6}\\}$ has $n_{3}-6$ vertices with lists of size 3 and
$n_{2}+4$ vertices with lists of size 2. Therefore $L$-choosability of $G$ can
be determined in time $O(3(1.3196)^{n_{3}-6+.5(n_{2}+4)})$ which is a subset
of $O(1.3196^{n_{3}+.5n_{2}})$, as desired.

Case 3: A vertex $v$ with list size 3 is adjacent to 4 vertices of lists of
size 3. We need to consider more subcases here compared to Case 1 and Case 2.
However, the idea of the proof is very similar to them. Therefore, to avoid
redundancy we skip some details.

At each subcase we consider the three possibilities on the color of $v$. When
$v$ gets color $i$ for $i\in\\{1,2,3\\}$, we reduce $L$-choosability of $G$ to
an $L^{\prime}$-choosability of a subgraph of $G$, which we call $G_{i}$. In
the following subcases we explain what $G_{i}$ is in each case, but we skip
the definition of $L^{\prime}$, as $L^{\prime}$ is naturally obtained from $L$
after removing the colors of the vertices with fixed colors from the list of
their neighbors.

By the structure of $G$ and since we may suppose Cases 1 and 2 do not happen,
the vertex $v$ has at least two neighbors with lists of size 2. Let $u_{1}$
and $u_{2}$ be two such neighbors of $v$. By symmetry suppose the list of
$u_{1}$ is $\\{1,2\\}$. Let the list on $u_{2}$ be $\\{c_{1},c_{2}\\}$.

Subcase 1: $u_{1}$ has another neighbor $u^{\prime}_{1}$ with list of size 3
(Figure 3).

Figure 3: When $u_{1}$ has another neighbor with list $\\{1,2,3\\}$.

Note that for the case that the color of $v$ is 1 or $2$, then we get only one
possible color for $u_{1}$, and as a result the list of $u^{\prime}_{1}$
decreases from size 3 to size 2 (Figure 4).

Figure 4: When $v$ gets color 1 in Subcase 1.

If $\\{c_{1},c_{2}\\}=\\{1,2\\}$ and $u_{2}$ has degree 1 in $G$, then let
$G_{1}=G_{2}=G-\\{v,u_{1},u_{2}\\}$ and $G_{3}=G-\\{v,u_{2}\\}$. Then by the
induction hypothesis we can determine $L$-choosability of $G$ in
$O((1.3196)^{n_{3}-6+.5(n_{2}+3)}+(1.3196)^{n_{3}-6+.5(n_{2}+3)}+(1.3196)^{n_{3}-5+.5(n_{2}+3)})$
time, which are both subsets of $O(1.3196^{n_{3}+.5n_{2}})$.

If $\\{c_{1},c_{2}\\}=\\{1,2\\}$ and $u_{2}$ has degree at least 2 in $G$,
then we may suppose $u_{2}$ has a neighbor with a list containing 2 (Otherwise
it must contain a neighbor with a list containing 1, which implies a similar
proof). In this case, let $G_{1}=G_{2}=G-\\{v,u_{1},u_{2}\\}$ and
$G_{3}=G-\\{v\\}$. By the induction hypothesis we can determine
$L$-choosability of $G$ in
$O((1.3196)^{n_{3}-6+.5(n_{2}+2)}+(1.3196)^{n_{3}-6+.5(n_{2}+3)}+(1.3196)^{n_{3}-5+.5(n_{2}+4)})$
time, which is a subset of $O(1.3196^{n_{3}+.5n_{2}})$, as desired.

If $\\{c_{1},c_{2}\\}\neq\\{1,2\\}$, then by symmetry we may suppose
$\\{c_{1},c_{2}\\}=\\{1,3\\}$. In this case let $G_{1}=G-\\{v,u_{1},u_{2}\\}$,
$G_{2}=G-\\{v,u_{1}\\}$, and $G_{3}=G-\\{v,u_{2}\\}$. By the induction
hypothesis we can determine $L$-choosability of $G$ in
$O((1.3196)^{n_{3}-6+.5(n_{2}+3)}+(1.3196)^{n_{3}-6+.5(n_{2}+4)}+(1.3196)^{n_{3}-5+.5(n_{2}+3)})$
time, which is a subset of $O(1.3196^{n_{3}+.5n_{2}})$, as desired.

Note that $u^{\prime}_{1}$ might be a neighbor of $v$. In this case when $v$
gets color 1 or 2, a neighbor of $v$ with list of size 3 (the vertex
$u^{\prime}$) reduces to a vertex with list of size 1. As a result, when
$\\{c_{1},c_{2}\\}=\\{1,2\\}$, we can determine $L$-choosability of $G$ in
$O((1.3196)^{n_{3}-5+.5(n_{2}+1)}+(1.3196)^{n_{3}-5+.5(n_{2}+1)}+(1.3196)^{n_{3}-5+.5(n_{2}+4)})$
time and when $\\{c_{1},c_{2}\\}\neq\\{1,2\\}$, we can determine
$L$-choosability of $G$ in
$O((1.3196)^{n_{3}-5+.5(n_{2}+2)}+(1.3196)^{n_{3}-5+.5(n_{2}+1)}+(1.3196)^{n_{3}-5+.5(n_{2}+3)})$
time, which are both subsets of $O(1.3196^{n_{3}+.5n_{2}})$, as desired.

A similar argument as the argument in Subcase 1 applies if $u_{2}$ has another
neighbor with a list of size 3. Therefore for the rest of cases we may suppose
the only neighbors of $u_{1}$ and $u_{2}$ with list of size 3 is $v$.

Subcase 2: Each of the vertices $u_{1}$ and $u_{2}$ has degree 2 in $G$. In
this case if $v$ gets color 1 or 2, then $u_{1}$ must have color 2 or 1,
respectively. If $v$ gets color 3, then $u_{1}$ keeps its list ($\\{1,2\\}$).
However it only needs to avoid one color that is the color of its other
neighbor. Therefore we can remove it from the graph, color the smaller graph,
if possible, and then extend the coloring to a coloring of $G$ by giving
$u_{1}$ an appropriate color in $\\{1,2\\}$. A similar argument applies to
vertex $u_{2}$.

Therefore in all the three possibilities of the color of $v$, we can reduce
the problem into an $L^{\prime}$-list choosability of the graph
$G-\\{v,u_{1},u_{2}\\}$. Hence by the induction hypothesis we can determine
$L$-choosability of $G$ in time $O(3(1.3196)^{n_{3}-5+.5(n_{2}+2)})$, which is
a subset of $O(1.3196^{n_{3}+.5n_{2}})$, as desired.

Therefore for the rest of cases we may suppose $u_{1}$ has degree at least 3
in $G$.

Subcase 3: $u_{1}$ has a neighbor $w_{1}$ with list $\\{1,2\\}$ and a neighbor
$w_{2}$ with list $\\{2,3\\}$, and the list on $u_{2}$ is either $\\{1,3\\}$
or $\\{2,3\\}$ (Figure 5).

Figure 5: When $L(w_{1})=\\{1,2\\}$ and $L(w_{2})=\\{2,3\\}$ and $3\in
L(u_{2})$.

If $v_{1}$ gets color 1, then we reduce the problem into a list choosability
of $G-\\{v,u_{1},w_{1},w_{2}\\}$ (Figure 6). If $v_{1}$ gets color 2, then we
reduce the problem into a list choosability of $G-\\{v,u_{1},w_{1}\\}$, and
when $v$ gets color 3, we reduce the problem into a list choosability of
$G-\\{v,u_{2}\\}$.

Figure 6: When $v$ gets color 1 in Subcase 3.

By the induction hypothesis it takes
$O((1.3196)^{n_{3}-5+.5(n_{2}+1)}+(1.3196)^{n_{3}-5+.5(n_{2}+2)}+(1.3196)^{n_{3}-5+.5(n_{2}+3)})$
time to determine $L$-choosability of $G$, which is a subset of
$O(1.3196^{n_{3}+.5n_{2}})$, as desired.

Subcase 4: $u_{1}$ has a neighbor $w_{1}$ with list $\\{1,2\\}$ and a neighbor
$w_{2}$ with list $\\{1,3\\}$, and the list on $u_{2}$ is either $\\{1,3\\}$
or $\\{2,3\\}$. The argument in this case is very similar to that in Subcase
3.

Subcase 5: $u_{1}$ has a neighbor $w_{1}$ with list $\\{1,2\\}$ and a neighbor
$w_{2}$ with list $\\{2,3\\}$, and the list on $u_{2}$ is $\\{1,2\\}$ (Figure
7).

Figure 7: When $L(w_{1})=L(u_{2})=\\{1,2\\}$ and $L(w_{2})=\\{2,3\\}$.

If $v_{1}$ gets color 1 (Figure 8), then we reduce the problem into a list
choosability of $G-\\{v,u_{1},w_{1},w_{2},u_{2}\\}$. If $v_{1}$ gets color 2,
then we reduce the problem into a list choosability of
$G-\\{v,u_{1},w_{1},u_{2}\\}$, and when $v$ gets color 3, we reduce the
problem into a list choosability of $G-\\{v\\}$. By the induction hypothesis
it takes
$O((1.3196)^{n_{3}-5+.5(n_{2})}+(1.3196)^{n_{3}-5+.5(n_{2}+1)}+(1.3196)^{n_{3}-5+.5(n_{2}+4)})$
time to determine $L$-choosability of $G$. Since
$(1.3196)^{n_{3}-5+.5(n_{2})}+(1.3196)^{n_{3}-5+.5(n_{2}+1)}+(1.3196)^{n_{3}-5+.5(n_{2}+4)}\leq
1.3196^{n_{3}+.5n_{2}}$ the assertion holds in this case.

Figure 8: When $v$ gets color 1 in Subcase 5.

Subcase 6: $u_{1}$ has a neighbor $w_{1}$ with list $\\{1,2\\}$ and a neighbor
$w_{2}$ with list $\\{1,3\\}$, and the list on $u_{2}$ is $\\{1,2\\}$. The
argument in this case is very similar to that in Subcase 5.

Subcase 7: $u_{1}$ has two neighbors $w_{1}$ and $w_{2}$ both with lists
$\\{1,2\\}$ and the list of $u_{2}$ is $\\{1,3\\}$ or $\\{2,3\\}$.

If $v_{1}$ gets color 1 or 2, then we reduce the problem into a list
choosability of $G-\\{v,u_{1},w_{1},w_{2}\\}$ and when $v$ gets color 3, we
reduce the problem into a list choosability of $G-\\{v,u_{2}\\}$. By the
induction hypothesis it takes
$O(2(1.3196)^{n_{3}-5+.5(n_{2}+1)}+(1.3196)^{n_{3}-5+.5(n_{2}+3)})$ time to
determine $L$-choosability of $G$, which is a subset of
$O(1.3196^{n_{3}+.5n_{2}})$, as desired.

Subcase 8: $u_{1}$ has two neighbors $w_{1}$ and $w_{2}$ both with lists
$\\{1,2\\}$ and the list of $u_{2}$ is $\\{1,2\\}$.

If $v_{1}$ gets color 1 or 2, then we reduce the problem into a list
choosability of $G-\\{v,u_{1},w_{1},w_{2},u_{2}\\}$ and when $v$ gets color 3,
we reduce the problem into a list choosability of $G-\\{v\\}$. By the
induction hypothesis it takes
$O(2(1.3196)^{n_{3}-5+.5(n_{2})}+(1.3196)^{n_{3}-5+.5(n_{2}+4)})$ time to
determine $L$-choosability of $G$, which is a subset of
$O(1.3196^{n_{3}+.5n_{2}})$, as desired.

Subcase 9: $u_{1}$ has a neighbor $w_{1}$ with list $\\{1,3\\}$ and a neighbor
$w_{2}$ with list $\\{2,3\\}$, and the list on $u_{2}$ is either $\\{1,3\\}$
or $\\{2,3\\}$. We may suppose the list on $u_{2}$ is $\\{1,3\\}$ (Figure 9).
The proof of the other case is similar.

Figure 9: When $L(w_{1})=\\{1,2\\}$ and $L(w_{2})=\\{1,3\\}$ and $3\in
L(u_{2})$.

For the cases that $v$ gets color 1, 2, or 3, we reduce the problem into
choosability problems of the smaller graphs $G-\\{v,u_{1},w_{2},u_{2}\\}$,
$G-\\{v,u_{1},w_{1}\\}$, and $G-\\{v,u_{2}\\}$, respectively. Figure 10
explains the case $v$ gets color 1.

Figure 10: When $v$ gets color 1 in Subcase 9.

As a result the induction hypothesis implies that $L$-choosability of $G$ can
be determined in time
$O((1.3196)^{n_{3}-5+.5(n_{2}+1)}+(1.3196)^{n_{3}-5+.5(n_{2}+2)}+(1.3196)^{n_{3}-5+.5(n_{2}+3)})$,
which is a subset of $O(1.3196^{n_{3}+.5n_{2}})$, as desired.

Subcase 10: $u_{1}$ has a neighbor $w_{1}$ with list $\\{1,3\\}$ and a
neighbor $w_{2}$ with list $\\{2,3\\}$, and the list on $u_{2}$ is
$\\{1,2\\}$.

If $u_{2}$ has degree 1 in $G$, then for the cases that $v$ gets color 1, 2,
or 3, we reduce the problem into choosability problems of the smaller graphs
$G-\\{v,u_{1},w_{2},u_{2}\\}$, $G-\\{v,u_{1},w_{1},u_{2}\\}$, and
$G-\\{v,u_{2}\\}$, respectively. As a result the induction hypothesis implies
that $L$-choosability of $G$ can be determined in time
$O(2(1.3196)^{n_{3}-5+.5(n_{2}+1)}+(1.3196)^{n_{3}-5+.5(n_{2}+3)})$, which is
a subset of $O(1.3196^{n_{3}+.5n_{2}})$, as desired.

If $u_{2}$ has degree more than 1 in $G$, then we may suppose a neighbor of
$u_{2}$ that is different from $v$ has color $1$ on his list. As a result, for
the cases that $v$ gets color 1, 2, or 3, we reduce the problem into
choosability problems of the smaller graphs $G-\\{v,u_{1},w_{2},u_{2}\\}$,
$G-\\{v,u_{1},w_{1},u_{2}\\}$, and $G-\\{v\\}$, respectively. As a result the
induction hypothesis implies that $L$-choosability of $G$ can be determined in
time
$O((1.3196)^{n_{3}-5+.5(n_{2}+1)}+(1.3196)^{n_{3}-5+.5(n_{2})}+(1.3196)^{n_{3}-5+.5(n_{2}+4)})$,
which is a subset of $O(1.3196^{n_{3}+.5n_{2}})$, as desired.

Subcase 11: $u_{1}$ has two neighbors $w_{1}$ and $w_{2}$ both with lists
$\\{1,3\\}$ or both with lists $\\{2,3\\}$ and the list of $u_{2}$ is
$\\{1,3\\}$ or $\\{2,3\\}$ (Figure 11).

Figure 11: When $L(w_{1})=L(w_{2})=L(u_{2})=\\{1,3\\}$.

We may suppose $w_{1}$ and $w_{2}$ both have lists $\\{1,3\\}$, the proof of
the other case is similar. We may also suppose that $u_{1}$ has no neighbor
with list $\\{2,3\\}$, since otherwise the above cases can be applied. For the
cases that $v$ gets color 1, 2, or 3, we reduce the problem into choosability
problems of the smaller graphs $G-\\{v,u_{1}\\}$,
$G-\\{v,u_{1},w_{1},w_{2}\\}$, and $G-\\{v,u_{1},u_{2}\\}$, respectively.
Figure 12 explains this for the case we give $v$ color $1$.

Figure 12: When $v$ gets color 1 in Subcase 11.

Note that for the case that $v$ gets color 3, we can give $u_{1}$ color 2
because none of its other neighbors’ list contain color 2. By the induction
hypothesis $L$-choosability of $G$ can be determined in time
$O((1.3196)^{n_{3}-5+.5(n_{2}+3)}+(1.3196)^{n_{3}-5+.5(n_{2}+1)}+(1.3196)^{n_{3}-5+.5(n_{2}+2)})$,
which is a subset of $O(1.3196^{n_{3}+.5n_{2}})$, as desired.

Subcase 12: $u_{1}$ has two neighbors $w_{1}$ and $w_{2}$ both with lists
$\\{1,3\\}$ or both with lists $\\{2,3\\}$ and the list of $u_{2}$ is
$\\{1,2\\}$.

We may suppose $w_{1}$ and $w_{2}$ both have lists $\\{1,3\\}$, the proof of
the other case is similar. We may also suppose that $u_{1}$ has no neighbor
with list $\\{2,3\\}$, since otherwise the above cases can be applied. For the
cases that $v$ gets color 1, 2, or 3, we reduce the problem into choosability
problems of the smaller graphs $G-\\{v,u_{1},u_{2}\\}$,
$G-\\{v,u_{1},w_{1},w_{2},u_{2}\\}$, and $G-\\{v,u_{1}\\}$, respectively. Note
that for the case that $v$ gets color 3, we can give $u_{1}$ color 2 because
none of its other neighbors’ list contain color 2. By the induction hypothesis
$L$-choosability of $G$ can be determined in time
$O((1.3196)^{n_{3}-5+.5(n_{2}+2)}+(1.3196)^{n_{3}-5+.5(n_{2})}+(1.3196)^{n_{3}-5+.5(n_{2}+3)})$,
which is at most $O(1.3196^{n_{3}+.5n_{2}})$, as desired.

Case 4: None of the above cases. Let $A$ be the set of vertices with lists of
size 2 in $G$ and let $B$ be the vertices with lists of size 3 in $G$. Since
we are supposing that none of the above cases happen, each vertex of $B$ has
at least 3 neighbors in $A$.

If there is a vertex in $A$ having at least 2 neighbors in $B$, call it
$a_{1}$. Now if there is a vertex in $A-\\{a_{1}\\}$ having at least 2
neighbors in $B-N(a_{1})$, then call this vertex $a_{2}$. At step $i$ if there
is a vertex in $A-\\{a_{1},\ldots,a_{i-1}\\}$ having at least two neighbors in
$B-\cup_{i=1}^{i-1}N(a_{i})$, name the vertex $a_{i}$. Continue the process
until no such vertex exists. Suppose the process stops at step $x_{1}$ and let
$X_{1}$ be the set of these vertices. i.e.
$X_{1}=\\{a_{1},\ldots,a_{x_{1}}\\}$.

Let $Y_{1}$ be the set of neighbors of $X_{1}$ in $B$ and let $X_{2}=A-X_{1}$,
$Y_{2}=B-Y_{1}$, $x_{2}=|X_{2}|$, $y_{1}=|Y_{1}|$, and $y_{2}=|Y_{2}|$ (Figure
13). By the choice of $X_{1}$ and $Y_{1}$ we have

$y_{1}\geq 2x_{1}.$

Note that each vertex in $X_{2}$ has at most one neighbor in $Y_{2}$, since
otherwise we can extend $X_{1}$ to a larger set. Moreover, each vertex in
$Y_{2}$ has at least three neighbors in $X_{2}$, because as we argued above
each vertex with a list of size 3 has at least three neighbors with lists of
size 2 (Figure 13). Therefore

$y_{2}\leq 3x_{2}.$

Figure 13: Partitioning $V(G)$ into vertices with lists of size 2 and size 3.

Now we break $L$-choosability of $G$ into list choosability of
$2^{x_{1}+x_{2}}$ smaller graphs such that each vertex in those graphs has a
list of size 1 or 2. In fact each vertex in $X_{1}$ has a list of size 2, so
it has two color options. Once we fix the coloring of the vertices in $X_{1}$,
the lists on the vertices in $Y_{1}$ go down to size 1 or 2. Moreover, for
each vertex in $Y_{2}$, we consider the two possibilities that the vertex gets
color 1 or another color. If the color of $v$ is not 1, then its list becomes
$\\{2,3\\}$, which has size 2. Each of the resulting $2^{x_{1}+y_{2}}$ graphs
has vertices of size at most 2. Hence by [2] we can determine in polynomial
time if it has a proper coloring from its lists or not. Hence the complexity
of determining if $G$ is $L$-choosable or not is $O(2^{x_{1}+y_{2}})$. Since
$y_{1}\geq 2x_{1}$ and $y_{2}\leq 3x_{2}$, we have

$2^{x_{1}}\leq 1.3196^{y_{1}+.5x_{1}}$

and

$2^{y_{2}}\leq 1.3196^{y_{2}+.5x_{2}}$

Therefore $O(2^{x_{1}+y_{2}})\subseteq
O(1.3196^{y_{1}+y_{2}+.5x_{1}+.5x_{2}})=O(1.3196^{n_{3}+.5n_{2}})$, as
desired.

## References

  * [1] R. Beigel and D. Eppstein, 3-coloring in time $O(1.3289^{n})$, J. Algorithms, 54:2, 168–204, 2005.
  * [2] A. Björklund, T. Husfeldt, and M. Koivisto, Set partitioning via inclusion–exclusion, SIAM J. Comput. 39 (2009), 546–563.
  * [3] N. Christofides, An Algorithm for the Chromatic Number of a Graph, Computer J., 14, 38–39, 1971.
  * [4] N. Crawford, S.Jahanbekam, K.Potika, Improved algorithm to determine 3-colorability of graphs with minimum degree at least 7, Discrete Applied Mathematics, to appear.
  * [5] R. E. Miller, J. W. Thatcher, and J.D. Bohlinger, Complexity of Computer Computations, New York: Plenum. pp. 85–103.
  * [6] J. Kratochvíla and Z. Tuza, Algorithmic complexity of list colorings, Discrete Applied Mathematics, Volume 50, Issue 3, 297–302, 1994.
  * [7] D. B. West, Introduction to Graph Theory, Second edition, Published by Prentice Hall 1996, 2001. ISBN 0-13-014400-2.