# Complexity of Grundy Coloring and Its Variants

Edouard Bonnet, Florent Foucaud, Eun Jung Kim, Florian Sikora

► To cite this version:

Edouard Bonnet, Florent Foucaud, Eun Jung Kim, Florian Sikora. Complexity of Grundy Coloring and Its Variants. 21st International Conference on Computing and Combinatorics, COCOON 2015, Aug 2015, Beijing, China. pp.109-120, 10.1007/978-3-319-21398-9_9. hal-01370531

HAL Id: hal-01370531

https://hal.science/hal-01370531v1

Submitted on 13 Feb 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Complexity of Grundy coloring and its variants

Édouard Bonnet¹,², Florent Foucaud*³, Eun Jung Kim¹, and Florian Sikora¹

¹ PSL, Université Paris-Dauphine, LAMSADE UMR CNRS 7243, France
{edouard.bonnet,eunjung.kim,florian.sikora}@dauphine.fr

² Hungarian Academy of Sciences

³ LIMOS UMR CNRS 6158, Université Blaise Pascal, France
florent.foucaud@gmail.com

**Abstract.** The Grundy number of a graph is the maximum number of colors used by the greedy coloring algorithm over all vertex orderings. In this paper, we study the computational complexity of GRUNDY COLORING, the problem of determining whether a given graph has Grundy number at least *k*. We show that GRUNDY COLORING can be solved in time $O*(2.443^n)$ on graphs of order *n*. While the problem is known to be solvable in time $f(k, w) \cdot n$ for graphs of treewidth *w*, we prove that under the Exponential Time Hypothesis, it cannot be computed in time $O*(c^w)$, for any constant *c*. We also study the parameterized complexity of GRUNDY COLORING parameterized by the number of colors, showing that it is in FPT for graphs including chordal graphs, claw-free graphs, and graphs excluding a fixed minor.

Finally, we consider two previously studied variants of GRUNDY COLORING, namely WEAK GRUNDY COLORING and CONNECTED GRUNDY COLORING. We show that WEAK GRUNDY COLORING is fixed-parameter tractable with respect to the weak Grundy number. In stark contrast, it turns out that checking whether a given graph has connected Grundy number at least *k* is NP-complete already for *k* = 7.

# 1 Introduction

A *k*-coloring of a graph *G* is a surjective mapping φ : *V*(*G*) → {1, ..., *k*} and we say *v* is colored with φ(*v*). A *k*-coloring φ is proper if any two adjacent vertices receive different colors in φ. The chromatic number χ(*G*) of *G* is the smallest *k* such that *G* has a *k*-coloring. Determining the chromatic number of a graph is the most fundamental problem in graph theory. Given a graph *G* and an ordering σ = *v*₁, ..., *v*ₙ of *V*(*G*), the first-fit algorithm colors vertex *v*ᵢ with the smallest color that is not present among the set of its neighbors within {*v*₁, ..., *v*ᵢ₋₁}. The Grundy number Γ(*G*) is the largest *k* such that *G* admits a vertex ordering on which the first-fit algorithm yields a proper *k*-coloring. First-fit is presumably the simplest heuristic to compute a proper coloring of a graph. In this sense, the Grundy number gives an algorithmic upper bound on the performance of any

<footnote>* This research was done while this author was a postdoctoral fellow at the Department of Mathematics of University of Johannesburg (South Africa) and at LAMSADE.</footnote>
heuristic for the chromatic number. This notion was first studied by Grundy in 1939 in the context of digraphs and games [11], and formally introduced 40 years later by Christen and Selkow [8]. Many works have studied the first-fit algorithm in connection with on-line coloring algorithms, see e.g. [21]. A natural relaxation of this concept is the weak Grundy number, introduced by Kierstead and Saoub [17], where the obtained coloring is not asked to be proper. A more restricted concept is the one of connected Grundy number, introduced by Benevides et al. [3], where the algorithm is given an additional “local” restriction: at each step, the subgraph induced by the colored vertices must be connected.

The goal of this paper is to advance the study of the computational complexity of determining the Grundy number, the weak Grundy number and the connected Grundy number of a graph.

Let us introduce the problems formally. Let $G$ be a graph and let $\sigma = v_1, \dots, v_n$ be an ordering of $V(G)$. A (not necessarily proper) $k$-coloring $\varphi: V(G) \to \{1, \dots, k\}$ of $G$ is a first-fit coloring with respect to $\sigma$ if for every vertex $v_i$ and every color $c$ with $c < \varphi(v_i)$, $v_i$ has a neighbor $v_j$ with $\varphi(v_j) = c$ for some $j < i$. In particular, $\varphi(v_1) = 1$. A vertex ordering $\sigma = v_1, \dots, v_n$ is connected if for every $i$, $1 \le i \le n$, the subgraph induced by $\{v_1, \dots, v_i\}$ is connected. A $k$-coloring $\varphi: V(G) \to \{1, \dots, k\}$ is called the (i) weak Grundy, (ii) Grundy, (iii) connected Grundy coloring of $G$, respectively, if it is a first-fit coloring with respect to some vertex ordering $\sigma$ such that (i) $\varphi$ and $\sigma$ has no restriction, (ii) $\varphi$ is proper, (iii) $\varphi$ is proper and $\sigma$ is connected, respectively.

The maximum number of colors used in a (weak, connected, respectively) Grundy coloring is called the (weak, connected, respectively) Grundy number and is denoted $\Gamma(G)$ ($\Gamma'(G)$ and $\Gamma_c(G)$, respectively). In this paper, we study the complexity of computing these invariants.

## GRUNDY COLORING

**Input:** A graph $G$, an integer $k$.

**Question:** Do we have $\Gamma(G) \ge k$?

The problems WEAK GRUNDY COLORING and CONNECTED GRUNDY COLORING are defined analogously.

Note that $\chi(G) \le \Gamma(G) \le \Delta(G) + 1$, where $\chi(G)$ is the chromatic number and $\Delta(G)$ is the maximum degree of $G$. However, the difference $\Gamma(G) - \chi(G)$ can be (arbitrarily) large, even for bipartite graphs. For example, the Grundy number of the tree of Figure 1 is 4, whereas its chromatic number is 2. Note that this is not the case for $\Gamma_c(G)$ for bipartite graphs, since $\Gamma_c(G) \le 2$ for any bipartite graph $G$ [3]. However, the difference $\Gamma_c(G) - \chi(G)$ can be (arbitrarily) large even for planar graphs [3].

*Previous results.* GRUNDY COLORING remains NP-complete on bipartite graphs [14] and their complements [25] (and hence claw-free graphs and $P_5$-free graphs), on chordal graphs [23], and on line graphs [13]. Certain graph classes admit polynomial-time algorithms. There is a linear-time algorithm for GRUNDY COLORING on trees [15]. This result was extended to graphs of bounded treewidth by Telle and Proskurowski [24], which proposed a dynamic
programming algorithm running in time $k^{O(w)}2^{O(kw)}n = O(n^{3w^2})$ for graphs of treewidth $w$ (in other words, their algorithm is in FPT for parameter $k+w$ and in XP for parameter $w$).$^4$ A polynomial-time algorithm for $P_4$-laden graphs, which contains all cographs as a subfamily, was given in [2].

Note that GRUNDY COLORING admits a polynomial-time algorithm when the number $k$ of colors is fixed [26], in other words, it is in XP for parameter $k$.

GRUNDY COLORING has polynomial-time constant-factor approximation algorithms for inputs that are interval graphs [12,21], complements of chordal graphs [12], complements of bipartite graphs [12] and bounded tolerance graphs [17]. In general, however, there is a constant $c > 1$ s.t. approximating GRUNDY COLORING within $c$ is impossible unless $\mathrm{NP} \subseteq \mathrm{RP}$ [18]. It is not known if a polynomial-time $o(n)$-factor approximation algorithm exists.

When parameterized by the graph's order minus the number of colors, GRUNDY COLORING was shown to be in FPT by Havet and Sempaio [14].

CONNECTED GRUNDY COLORING was introduced by Benevides et al. [3], who proved it to be NP-complete, even for chordal graphs and for co-bipartite graphs. WEAK GRUNDY COLORING is NP-complete [10].

*Our results.* As pointed out in [24], no (extended) monadic second order expression is known for the property "$\Gamma(G) \ge k$". Therefore it is not clear whether the algorithm of [24] can be improved, e.g. to an algorithm of running time $f(w) \cdot \mathrm{poly}(n)$. Nevertheless, on general graphs, we show that GRUNDY COLORING can be solved in time $O^*(2.443^n)$.

As a lower bound to the positive algorithmic bounds, we show that under the Exponential Time Hypothesis (ETH) [16], an $O(c^w \cdot \mathrm{poly}(n))$-time algorithm for GRUNDY COLORING does not exist (for any fixed constant $c$). Hence the exponent $n$ cannot be replaced by the treewidth in our $O^*(2.443^n)$-time algorithm.

We also study the parameterized complexity of GRUNDY COLORING parameterized by the number of colors, showing that it is in FPT for graphs including chordal graphs, claw-free graphs, and graphs excluding a fixed minor.

Finally, we show that WEAK GRUNDY COLORING and CONNECTED GRUNDY COLORING exhibit opposite computational behavior when viewed through the lens of parameterized complexity (for the parameter "number of colors"). While WEAK GRUNDY COLORING is shown to be FPT on general graphs, CONNECTED GRUNDY COLORING is NP-complete even when $k=7$, i.e. does not belong to XP (it is the only of the three studied problems to be in this case). Note that the known NP-hardness proof for CONNECTED GRUNDY COLORING was only for an unbounded number of colors [3].

Due to space constraints, some proofs are deferred to the full version of the paper [6].

<footnote n="4">⁴ The first running time is not explicitly stated in [24] but follows from their meta-theorem. The second one is deduced by the authors of [24] from the first one by bounding $k$ by $w \log_2 n + 1$.</footnote>
## 2 Preliminaries

We defer many (classic) technical definitions to the full version [6], and only give the ones related to Grundy colorings. Given a graph $G$, a *colored witness* of height $\ell$, or simply called an $\ell$-witness, is a subgraph $G'$ of $G$, which comes with a partition $\mathcal{W} = W_1 \uplus \cdots \uplus W_\ell$ of $V(G')$ such that for every $i$ in $1, \dots, \ell$ $(1) W_i \neq \emptyset$, and $(2) W_i$ is an independent dominating set of $G[W_i \cup \cdots \cup W_\ell]$. The cell $W_i$ under $\mathcal{W}$ is called the *color class* of color $i$. A witness $G'$ of height $\ell$ is said to be *minimal* if for every $u \in V(G')$, $G' - u$ with the partition $\mathcal{W}|_{V(G') - \{u\}}$ is not an $\ell$-witness.

**Observation 1.** For any graph $G$, $\Gamma(G) \ge k$ if and only if $G$ allows a minimal $k$-witness.

**Observation 2.** A minimal $k$-witness has a vertex of degree $k-1$ (the root), order at most $2^{k-1}$, and is included in the distance-$k$ neighborhood of the root.

By these observations, $k$-GRUNDY COLORING can be solved by checking, for every subset of $2^{k-1}$ vertices, if it contains a $k$-witness as an induced subgraph:

**Corollary 3 ([26]).** GRUNDY COLORING can be solved in time $f(k)n^{2^{k-1}}$, i.e. GRUNDY COLORING parameterized by the number $k$ of colors is in XP.

**Observation 4.** In any Grundy coloring of $G$, a vertex with degree $d$ cannot be colored with color $d+2$ or larger.

**Proposition 5.** Let $G$ be a graph with a minimal Grundy coloring achieving color $k$ and let $W$ be the corresponding minimal witness. Then, if a vertex $u$ of $W$ is colored with $k' < k$, $u$ has a neighbor colored with some color $k'', k'' > k'$.

*Proof.* If not, one could remove $u$ from the witness, a contradiction. □

**Lemma 6.** Let $G$ be a graph and let $G'$ be the corresponding minimal $\ell$-witness with the partition $\mathcal{W} := W_1 \uplus \cdots \uplus W_\ell$. Then, $W_i$ is an independent set which dominates the set $\bigcup_{j \in [i+1, \ell]} W_j$ (and no proper subset of $W_i$ has this property). In particular, $W_1$ is a minimal independent dominating set of $V(G')$.

For each $i \in [\ell]$, let $t_i$ be a rooted tree. We define $v[t_1, t_2, \dots, t_\ell]$ as the tree rooted at node $v$ where $v$ is linked to the root of each tree $t_i$. The set $(T_k)_{k \ge 1}$ is a family of rooted trees (known as *binomial trees*) defined as follows (see Figure 1 for an illustration):

- $T_1$ consist only of one node (incidentally the root), and

- $\forall k \ge 1, T_{k+1} = v[T_1, T_2, \dots, T_k]$.

In a tree $T_k$ with root $v$, for each $i \in [k]$, $v(i)$ denotes the root of $T_i$ (i.e. the $i$-th child of $v$).

We now show a useful lemma about Grundy colorings of the tree $T_k$.
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** The binomial tree $T_4$, where numbers denote the color of each vertex in a first-fit proper coloring with largest number of colors.</figcaption></figure>

**Lemma 7.** The Grundy number of $T_k$ is $k$. Moreover, there are exactly two Grundy colorings achieving color $k$, and a unique coloring if we impose that the root is colored $k$.

The following result of Chang and Hsu [7] will prove useful:

**Theorem 8 ([7]).** Let $G$ be a graph on $n$ vertices for which every subgraph $H$ has at most $d|V(H)|$ edges. Then $\Gamma(G) \le \log_{d+1/d}(n) + 2$.

# 3 Grundy Coloring: algorithms and complexity

## 3.1 An exact algorithm

A straightforward way to solve GRUNDY COLORING is to enumerate all possible orderings of the vertex set and to check whether the greedy algorithm uses at least $k$ colors. This is a $\Theta(n!)$-time algorithm. A natural question is whether there is a faster exact algorithm. We now give such an algorithm.

We rely on two observations: (a) in a colored witness, every color class $W_i$ is an independent dominating set in $G[\bigcup_{j \ge i} W_j]$ (Lemma 6), and (b) any independent dominating set is a maximal independent set (and vice versa). The algorithm is obtained by dynamic programming over subsets, and uses an algorithm which enumerates all maximal independent sets.

**Theorem 9.** GRUNDY COLORING can be solved in time $O^*(2.44225^n)$.

*Proof.* Let $G = (V, E)$ be a graph. We present a dynamic programming algorithm to compute $\Gamma(G)$. For simplicity, given $S \subseteq V$, we denote the Grundy number of the induced subgraph $G[S]$ by $\Gamma(S)$. We recursively fill a table $\Gamma^*(S)$ over the subset lattice $(2^V, \subseteq)$ of $V$ in a bottom-up manner starting from $S = \emptyset$. The base case of the recursion is $\Gamma^*(\emptyset) = 0$. The recursive formula is given as

$$ \Gamma^*(S) = \max\{\Gamma^*(S\setminus X)+1 \mid X \subseteq S \text{ is an independent dominating set of } G[S]\}. $$

Now let us show by induction on $|S|$ that $\Gamma^*(S) = \Gamma(S)$ for all $S \subseteq V$. The assertion trivially holds for the base case. Consider a nonempty subset $S \subseteq V$; by induction hypothesis, $\Gamma^*(S') = \Gamma(S')$ for all $S' \subset S$. Let $X$ be a subset of $S$ achieving $\Gamma^*(S) = \Gamma^*(S \setminus X) + 1$ and $X'$ be the set of the color class 1 in the ordering achieving the Grundy number $\Gamma(S)$.
Let us first see that $\Gamma^*(S) \leq \Gamma(S)$. By induction hypothesis we have $\Gamma^*(S \setminus X) = \Gamma(S \setminus X)$. Consider a vertex ordering $\sigma$ on $S \setminus X$ achieving $\Gamma(S \setminus X)$. Augmenting $\sigma$ by placing all vertices of $X$ at the beginning of the sequence yields a (set of) vertex ordering(s). Since $X$ is an independent set, the first-fit algorithm gives color 1 to all vertices in $X$, and since $X$ is also a dominating set for $S \setminus X$, no vertex of $S \setminus X$ receives color 1. Therefore, the first-fit algorithm on such ordering uses $\Gamma(S \setminus X) + 1$ colors. We deduce that $\Gamma(S) \geq \Gamma(S \setminus X) + 1 = \Gamma^*(S \setminus X) + 1 = \Gamma^*(S)$.

To see that $\Gamma^*(S) \geq \Gamma(S)$, we first observe that $\Gamma(S \setminus X') \geq \Gamma(S) - 1$. Indeed, the use of the optimal ordering of $S$ ignoring vertices of $X'$ on $S \setminus X'$ yields the color $\Gamma(S) - 1$. We deduce that $\Gamma(S) \leq \Gamma(S \setminus X') + 1 = \Gamma^*(S \setminus X') + 1 \leq \Gamma^*(S \setminus X) + 1 = \Gamma^*(S)$.

As a minimal independent dominating set is a maximal independent set, we can estimate the computation of the table by restricting $X$ to the family of maximal independent sets of $G[S]$. On an $n$-vertex graph, one can enumerate all maximal independent sets in time $O(1.44225^n)$ [20]. Checking whether a given set is a minimal independent set is polynomial and thus, the number of execution steps is dominated (up to a polynomial factor) by the number of recursion steps taken. This is

$$ \sum_{i=0}^{n} \binom{n}{i} \cdot 1.44225^i = (1 + 1.44225)^n. $$

□

We leave as an open question to improve this running time. However, we note that the *fast subset convolution* technique [4] does not seem to be directly applicable.

## 3.2 Lower bound on the treewidth dependency

Let us recall that GRUNDY COLORING is known to be in $\mathbb{XP}$ for the parameter treewidth, but its membership in FPT remains open.

The following result is inspired by ideas in [19] for proving near-optimality of known algorithm on bounded treewidth graphs. Unlike [19] which is based on the *Strong* ETH, our result is based on the ETH.

**Theorem 10.** Under the ETH, for any constant $c$, GRUNDY COLORING is not solvable in time $O^*(c^w)$ on graphs with feedback vertex set number (and hence treewidth) at most $w$.

## 3.3 Grundy Coloring on special graph classes

For each fixed $k$, GRUNDY COLORING can be solved in polynomial time [26] and thus GRUNDY COLORING parameterized by the number of colors is in $\mathbb{XP}$. However, it is unknown whether it is in FPT for this parameter. We will next
show several positive results for *H*-minor-free, chordal and claw-free graphs. Note that GRUNDY COLORING is NP-complete on chordal graphs [23] and on claw-free graphs [25].

We first observe that the XP algorithm of [24] implies a pseudo-polynomial-time algorithm on apex-minor-free graphs (such as planar graphs).

**Proposition 11.** GRUNDY COLORING is $n^{O(\log^2 n)}$-time solvable on apex-minor-free graphs.

**Proposition 12.** GRUNDY COLORING parameterized by the number of colors is in FPT for the class of graphs excluding a fixed graph *H* as a minor.

*Proof.* Notice that *G* contains a *k*-witness *H* as an induced subgraph if and only if $\Gamma(G) \ge k$. We can check, for every *k*-witness *H*, whether the input graph *G* contains *H* as an induced subgraph. By Observation 1, it suffices to test only the minimal *k*-witnesses. The number of minimal *k*-witnesses is bounded by some function of *k* and *H*-INDUCED SUBGRAPH ISOMORPHISM is in FPT when parameterized by $|V(H)|$ on graphs excluding *H* as a minor [9]. Therefore, one can check if $\Gamma(G) \ge k$ by solving *H*-INDUCED SUBGRAPH ISOMORPHISM for all minimal *k*-witnesses *H*. $\square$

**Proposition 13.** Let *C* be a graph class for which every member *G* satisfies $tw(G) \le f(\Gamma(G))$ for some function *f*. Then, GRUNDY COLORING parameterized by the number of colors is in FPT on *C*. In particular, GRUNDY COLORING is in FPT on chordal graphs.

*Proof.* Since GRUNDY COLORING is in FPT for parameter combination of the number of colors and the treewidth [24], the first claim is immediate. Moreover $\omega(G) \le \Gamma(G)$, hence if $tw(G) \le f(\omega(G))$ we have $tw(G) \le f(\Gamma(G))$. For any chordal graph $G$, $tw(G) = \omega(G) - 1$ [5]. $\square$

**Proposition 14.** GRUNDY COLORING can be solved in time $O(nk^{\Delta^{k+1}}) = n\Delta^{O(\Delta)}$ for graphs of maximum degree $\Delta$.

*Proof.* Observation 2 implies that one can enumerate every distance-*k*-neighbourhood of each vertex, test every *k*-coloring of this neighborhood, and check if it is a valid Grundy *k*-coloring. Every such neighborhood has size at most $\Delta^{k+1} \le \Delta^{\Delta+3}$ since by Observation 4, $k \le \Delta + 2$. There are at most $k^x$ *k*-colorings of a set of *x* elements. $\square$

**Corollary 15.** Let *C* be a graph class for which every member *G* satisfies $\Delta(G) \le f(\Gamma(G))$ for some function *f*. Then, GRUNDY COLORING parameterized by the number of colors is in FPT for graphs in *C*. In particular, this holds for the class of claw-free graphs.

*Proof.* Straightforward by Proposition 14. Moreover, let *G* be a claw-free graph, and consider a vertex *v* of degree $\Delta(G)$. Since *G* is claw-free, the subgraph induced by the neighbors of *v* has independence number at most 2, and hence $\Gamma(G) \ge \chi(G) \ge \chi(N(v)) \ge \frac{\Delta(G)}{2}$. $\square$
## 4 Weak and connected Grundy coloring

Among the three versions of GRUNDY COLORING we consider in this paper, WEAK GRUNDY COLORING is the least constrained while CONNECTED GRUNDY COLORING appears to be the most constrained one. This intuition turns out to be true when it comes to their parameterized complexity. When parameterized by the number of colors, WEAK GRUNDY COLORING is in FPT while CONNECTED GRUNDY COLORING does not belong to XP.

We recall that WEAK GRUNDY COLORING is NP-complete [10].

**Theorem 16.** WEAK GRUNDY COLORING parameterized by number of colors is in FPT.

The FPT-algorithm is based on the idea of *color-coding* by Alon et al. [1]. The height of a minimal witness for $\Gamma' \ge k$ is bounded by a function of $k$. Since those vertices of the same color do not need to induce an independent set, a random coloring will identify a *colorful* minimal witness with a good probability.

We also remark that the approach used to prove Theorem 16 does not work for GRUNDY COLORING because there is no control on the fact that a color class is an independent set.

Minimal connected Grundy $k$-witnesses, contrary to minimal Grundy $k$-witnesses (Observation 2), have arbitrarily large order: for instance, the cycle $C_n$ of order $n$ ($n > 4$, $n$ odd) has a Grundy 3-witness of order 4, but its unique connected Grundy 3-witness is of order $n$: the whole cycle.

Observe that $\Gamma_c(G) \le 2$ if and only if $G$ is bipartite. Hence, CONNECTED GRUNDY COLORING is polynomial-time solvable for any $k \le 3$. However, we will now show that this is not the case for larger values of $k$, contrary to GRUNDY COLORING (Corollary 3). Hence, the parameterized version of the problem does not belong to XP.

**Theorem 17.** CONNECTED GRUNDY COLORING is NP-hard even for $k = 7$.

*Proof.* We give a reduction from 3-SAT 3-OCC, an NP-complete restriction of 3-SAT where each variable appears in at most three clauses [22], to CONNECTED GRUNDY COLORING with $k = 7$. We first give the intuition of the reduction. The construction consists of a tree-like graph of constant order (resembling binomial tree $T_6$) whose root is adjacent to two vertices of a $K_6$ (this constitutes $W$) and contains three special vertices $a_4$, $a_{21}$, and $a_{24}$ (which will have to be colored with colors 1, 3, and 2 respectively), a connected graph $P_1$ which encodes the variables and a path $P_2$ which encodes the clauses. One in every three vertices of $P_2$ is adjacent to $a_4$, $a_{21}$ and $a_{24}$. To achieve color 7, we will need to color those vertices with color strictly greater than 3. This will be possible if and only if the assignment corresponding to the coloring of $P_1$ satisfies all the clauses.

We now formally describe the construction. Let $\phi = (X = \{x_1, \dots, x_n\}, C = \{C_1, \dots, C_m\})$ be an instance of 3-SAT 3-OCC where no variable appears always as the same literal. $P_1 = (\{i_1, i_2, v\} \cup \{v_i, \bar{v}_i \mid i \in [n]\}, \{\{i_1, i_2\}, \{i_2, v\}\} \cup \{\{v, v_i\} \cup \{v, \bar{v}_i\} \mid i \in [n]\})$ consists of $n$ triangles sharing the vertex $v$.
$P_2 = (\{p_j \mid j \in [3m-1]\}, \{\{p_j, p_{j+1}\} \mid j \in [3m-2]\})$ consists of a path of length $3m-1$. For each $j \in [m]$ and $i \in [n]$, $c_j \stackrel{def}{=} p_{3j-1}$ is adjacent to $v_i$ if $x_i$ appears positively in $C_j$, and is adjacent to $\bar{v}_i$ if $x_i$ appears negatively in $C_j$. For each $j \in [m]$, $c_j$ is adjacent to $a_4, a_{21}$, and $a_{24}$.

<figure><img src="image_3.png" /><figcaption>**Fig. 2.** $P_1$ and $P_2$ for the instance $\{x_1 \lor \neg x_2 \lor x_3\}, \{x_1 \lor x_2 \lor \neg x_4\}, \{\neg x_1 \lor x_3 \lor x_4\}, \{x_2 \lor \neg x_3 \lor x_4\}$.</figcaption></figure>

Intuitively, setting a literal to true consists of coloring the corresponding vertices with 3. Therefore, a clause $C_j$ is satisfied if $c_j$ has a 3 among its neighbors. To actually satisfy a clause, one has to color $c_j$ with 4 or higher. Thus, $c_j$ must also see a 2 in its neighborhood. We will show that the unique way of doing so is to color $p_{3j-2}$ with 2, so all the clauses have to be checked along the path $P_2$.

We give, in Figure 3, a coloring of $P_1$ corresponding to a truth assignment of the instance SAT formula. One can check that when going along $P_2$ all the $c_j$'s are colored with color 4.

<figure><img src="image_4.png" /><figcaption>**Fig. 3.** A connected Grundy coloring such that all the $c_j$'s are colored with color at least 4.</figcaption></figure>

The constant gadget $W$ is depicted in Figure 4. The waves between $a_4$ and $a_6$ and between $a_9$ and $a_{11}$ correspond, respectively, to the gadgets encoding the variables ($P_1$) and the clauses ($P_2$) described above and drawn in Figure 2. A connected Grundy coloring achieving color 7 is given in Figure 5 provided that going from $a_9$ to $a_{11}$ can be done without coloring any vertex $c_j$ with color 2 or less.
<figure><img src="image_5.png" /><figcaption>**Fig. 4.** The constant gadget. The doubly-circled vertices are adjacent to all the $c_j$'s ($j \in [m]$).</figcaption></figure>

<caption>**Fig. 5.** A connected Grundy coloring of the constant gadget achieving color 7. The order is given by the sequence $(a_i)_{1 \le i \le 33}$.</caption>

In the following claims, we use extensively Observation 1 which states that a vertex with degree $d$ gets color at most $d+1$. We observe that coloring a vertex of degree $d$ with color $d+1$ is useful only if we want to achieve color $d+1$. Indeed, otherwise, the vertex has all its neighbors already colored and cannot be used in the sequel. Moreover, if one wants to color a neighbor $y$ of a vertex $x$ in order to color $x$ with a higher color, $y$ cannot receive a color greater than its degree $d(y)$. Hence, the only vertices that could achieve color $k$ are vertices of degree at least $k-1$ having at least one neighbor of degree at least $k-1$.

In the sequel, we call *doubly-circled vertices* the special vertices $a_4, a_{21}$ and $a_{24}$, as they are doubly-circled in our figures.

**Claim 17.A.** To achieve color 7, $a_{27}$ needs to be colored with color 6 (while for all $i \in [28, 33]$, $a_i$ is still uncolored).

**Claim 17.B.** Vertices $a_{26}, a_{22}, a_{25}, a_{23}, a_{15}$ must receive color 1, 2, 3, 4, 5 respectively.

**Claim 17.C.** Vertex $a_7$ must receive color 4.

**Claim 17.D.** Vertex $a_3$ must receive color 3.

Claim 17.D has further consequences: we must start the connected Grundy coloring by giving colors 1 and 2 to $a_1$ and $a_2$. The only follow-up, for connectivity reasons, is then to color $a_3$ with color 3 and $a_4$ with color 1. Thus, vertices $a_5$ and $a_6$ has to be colored with colors 2 and 1 respectively (so that $a_7$ can be colored 4). As, by Claim 17.B, $a_{25}$ must receive color 3, $a_{24}$ must receive color 2 (since $a_4$ has already color 1), so $a_{18}$ must be colored 1.
**Claim 17.E.** Vertex $a_{21}$ must receive color 3.

**Claim 17.F.** The unique way of coloring $a_{11}$ with color 1 without coloring any vertex $c_j$ with color 1, 2, or 3 is to color all the $c_j$'s for each $j \in [m]$.

We remark that opposite literals are adjacent, so for each $i \in [n]$, only one of $v_i$ and $\overline{v_i}$ can be colored with color 3. We interpret coloring $v_i$ with 3 as setting $x_i$ to true and coloring $\overline{v_i}$ with 3 as setting $x_i$ to false.

**Claim 17.G.** To color each $c_j$ ($j \in [m]$) of the path $P_2$ with a color at least 4, the SAT formula must be satisfiable.

So, to achieve color 7 in a connected Grundy coloring, the SAT formula must be satisfiable. The reverse direction consists of completing the coloring by giving $a_{13}$ color 1 and $a_{14}$ color 2, as shown in Figure 3 and Figure 5. $\square$

# 5 Concluding remarks and questions

We presented several positive and negative results concerning GRUNDY COLORING and two of its variants. To conclude this article, we suggest some questions which might be useful as a guide for further studies.

There is a gap between the $f(k, w) \cdot n$ (and XP) algorithm of [24] and the lower bound of Theorem 10. Is GRUNDY COLORING in FPT when parameterized by treewidth? Two simpler questions are whether there is a better $f(k, w)\text{poly}(n)$ algorithm (for example with $f(k, w) = k^{O(w)}$), and whether GRUNDY COLORING is in FPT when parameterized by the feedback vertex set number (it is easy to see that it is the case when parameterized by the vertex cover number).

GRUNDY COLORING (parameterized by the number of colors) is in XP, and we showed it to be in FPT on many important graph classes. Yet, the question whether it is in FPT or W[1]-hard remains unsolved. A perhaps more accessible research direction is to settle this question on bipartite graphs.

It would also be interesting to determine the (classic) complexity of GRUNDY COLORING on interval graphs. Also, we saw that the algorithm of [24] implies a pseudo-polynomial algorithm for planar (even apex-minor-free) graphs, making it unlikely to be NP-complete on this class. Is there a polynomial-time algorithm?

Concerning CONNECTED GRUNDY COLORING, we showed that it becomes NP-complete for $k = 7$. As CONNECTED GRUNDY COLORING is polynomial-time solvable for $k \le 3$, its complexity status for $4 \le k \le 6$ and/or on restricted graph classes remains open.

# References

1. N. Alon, R. Yuster, and U. Zwick. Color-coding. *Journal of the ACM*, 42(4):844–856, 1995.

2. J. Araujo and C. Linhares Sales. On the Grundy number of graphs with few $P_4$'s. *Discrete Applied Mathematics*, 160(18):2514–2522, 2012.
3. F. Benevides, V. Campos, M. Dourado, S. Griffiths, R. Morris, L. Sampaio, and A. Silva. Connected greedy colourings. In *LATIN 2014*, volume 8392 of LNCS, pages 433–441. Springer, 2014.

4. A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto. Fourier meets Möbius: fast subset convolution. In *Proc. 39th Annual ACM Symposium on Theory of Computing*, STOC '07, pages 67–74. ACM, 2007.

5. H. L. Bodlaender. A tourist guide through treewidth. *Acta Cybernetica*, 11(1-2):1–21, 1993.

6. E. Bonnet, F. Foucaud, E. J. Kim, and F. Sikora. Complexity of grundy coloring and its variants. *CoRR*, abs/1407.5336, 2014.

7. G. J. Chang and H.-C. Hsu. First-fit chromatic numbers of $d$-degenerate graphs. *Discrete Mathematics*, 312(12-13):2088 – 2090, 2012.

8. C. A. Christen and S. M. Selkow. Some perfect coloring properties of graphs. *Journal of Combinatorial Theory, Series B*, 27(1):49 – 59, 1979.

9. J. Flum and M. Grohe. Fixed-parameter tractability, definability, and model-checking. *SIAM Journal on Computing*, 31(1):113–145, 2001.

10. N. Goyal and S. Vishwanathan. NP-completeness of undirected Grundy numbering and related problems. Manuscript, 1997.

11. P. M. Grundy. Mathematics and games. *Eureka*, 2:6–8, 1939.

12. A. Gyárfás and J. Lehel. On-line and first fit colorings of graphs. *Journal of Graph Theory*, 12(2):217–227, 1988.

13. F. Havet, A. K. Maia, and M.-L. Yu. Complexity of greedy edge-colouring. Research report RR-8171, INRIA, Dec. 2012.

14. F. Havet and L. Sampaio. On the Grundy and $b$-chromatic numbers of a graph. *Algorithmica*, 65(4):885–899, 2013.

15. S. M. Hedetniemi, S. T. Hedetniemi, and T. Beyer. A linear algorithm for the Grundy (coloring) number of a tree. *Congressus Numerantium*, 36:351–363, 1982.

16. R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity? *Journal of Computer and System Sciences*, 63(4):512–530, Dec. 2001.

17. H. A. Kierstead and K. R. Saoub. First-fit coloring of bounded tolerance graphs. *Discrete Applied Mathematics*, 159(7):605–611, 2011.

18. G. Kortsarz. A lower bound for approximating Grundy numbering. *Discrete Mathematics & Theoretical Computer Science*, 9(1), 2007.

19. D. Lokshtanov, D. Marx, and S. Saurabh. Known algorithms on graphs of bounded treewidth are probably optimal. In *Proc. 22nd Annual ACM-SIAM Symposium on Discrete Algorithms*, SODA '11, pages 777–789. SIAM, 2011.

20. J. Moon and L. Moser. On cliques in graphs. *Israel Journal of Mathematics*, 3(1):23–28, Mar. 1965.

21. N. S. Narayanaswamy and R. S. Babu. A note on first-fit coloring of interval graphs. *Order*, 25(1):49–53, 2008.

22. C. H. Papadimitriou. *Computational complexity*. Addison-Wesley, 1994.

23. L. Sampaio. *Algorithmic aspects of graph colouring heuristics*. PhD thesis, University of Nice-Sophia Antipolis, November 2012.

24. J. A. Telle and A. Proskurowski. Algorithms for vertex partitioning problems on partial $k$-trees. *SIAM Journal on Discrete Mathematics*, 10(4):529–550, 1997.

25. M. Zaker. The Grundy chromatic number of the complement of bipartite graphs. *Australasian Journal of Combinatorics*, 31:325–329, 2005.

26. M. Zaker. Results on the Grundy chromatic number of graphs. *Discrete Mathematics*, 306(23):3166–3173, 2006.