Question 21: In this question, we use [3] to denote {1, 2, 3}. Let G …

In this question, we use $[3]$ to denote $\{1, 2, 3\}$.

Let $G$ be a simple undirected finite graph. A function $f : V(G) \to [3]$ is called a proper 3-coloring of $G$ if no two adjacent vertices in $G$ have the same image under $f$. You can imagine $f$ coloring the vertices of the graph with colors 1, 2, and 3 (all vertices that have image 1 under $f$ are 'colored' 1, and so on); and such a coloring is proper if and only if there are no edges between vertices that have the same color.

In this question, we will explore ideas involving building up a DP-based solution for this problem for graphs of bounded treewidth using nice tree decompositions.

Let $\mathcal{T}(T, \{X_t\}_{t \in V(T)})$ be a rooted nice tree decomposition of $G$. For every node $t \in V(T)$, let $T_t$ denote the subtree of $T$ rooted at $t$.

For every node $x \in V(T)$ and every function $\chi : X_x \to [3]$, let $f(x, \chi)$ be defined as follows:

$f(x, \chi) := \text{TRUE}$ if there exists a function $\sigma : \bigcup_{\beta \in V(T_x)} X_\beta \to [3]$ such that

• $\forall u \in X_x : \ \big(\chi(u) = \sigma(u)\big)$
• No two adjacent vertices in $G\left[\bigcup_{\beta \in V(T_x)} X_\beta\right]$ have the same image under $\sigma$.

Otherwise, $f(x, \chi) := \text{FALSE}$.

The intuition for these definitions is the following. Fix a node $x \in V(T)$. Then $\chi$ describes a 3-coloring of the vertices in the bag $X_x$, which is not necessarily a proper 3-coloring. The function $f(x, \chi)$ describes if $\chi$ can be extended to a proper 3-coloring of the vertices in the subtree of $T$ rooted at $x$.

Now, let $v \in V(G)$. Let $a, b \in V(T)$ such that $v$ is introduced at $a$, and $b$ is the child of $a$.

Let $\theta : X_a \to [3]$ be a function such that

$\forall y \in X_a \cap N_G(v) : \quad \big(\theta(y) \neq \theta(v)\big)$

In other words, $\theta$ is a three-coloring of $X_a$ which ensures that the color of $v$ is different from the color of any of its neighbors in $X_a$.

Let $\theta' : X_b \to [3]$ be defined as follows:

$\forall y \in X_b : \quad \theta'(y) := \theta(y)$

Note that $X_b = X_a \cup \{v\}$ and thus $\theta'$ is simply the projection of $\theta$ on $X_b$.

Let $w \in V(G)$. Let $c, d \in V(T)$ such that $w$ is forgotten at $c$, and $d$ is the child of $c$.

In other words, $X_c = X_d \setminus \{w\}$.

Let $\psi : X_c \to [3]$ be a function. For every $i \in [3]$, let $\psi'_i : X_d \to [3]$ be defined as follows:

$\begin{aligned} \forall y \in X_d \setminus \{w\} : \quad & \psi'_i(y) := \psi(y) \\ & \psi'_i(w) := i \end{aligned}$

To explain this, assume that $\psi$ is a given 3-coloring of the parent node $X_c$. Now we define three colorings that extend $\psi$ in the child node $X_d$. For a fixed color $i \in [3]$, we are coloring every vertex in $X_d$ other than $w$ in the same way that it was colored in $X_c$ under $\psi$, and we are coloring $w$ with color $i$.

Let $e, g, h \in V(T)$ such that $e$ is a join node, and $g$ and $h$ are the children of $e$, and let $\lambda : X_e \to [3]$.

Based on the above data, answer the given subquestions.