Parameterized Saga of First-Fit and Last-Fit Coloring

Agrawal, Akanksha; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Verma, Shaily

doi:10.4230/LIPIcs.STACS.2025.5

Parameterized Saga of First-Fit and Last-Fit Coloring

Akanksha Agrawal

Indian Institute of Technology Madras, India Daniel Lokshtanov

University of California, Santa Barbara,CA, USA Fahad Panolan

School of Computer Science, University of Leeds, UK Saket Saurabh

The Institute of Mathematical Sciences, HBNI, Chennai, India
Department of Informatics, University of Bergen, Norway Shaily Verma

Algorithm Engineering Group, Hasso Plattner Institute, Potsdam, Germany

Abstract

The classic greedy coloring algorithm considers the vertices of an input graph $G$ in a given order and assigns the first available color to each vertex $v$ in $G$ . In the Grundy Coloring problem, the task is to find an ordering of the vertices that will force the greedy algorithm to use as many colors as possible. In the Partial Grundy Coloring, the task is also to color the graph using as many colors as possible. This time, however, we may select both the ordering in which the vertices are considered and which color to assign the vertex. The only constraint is that the color assigned to a vertex $v$ is a color previously used for another vertex if such a color is available.

Whether Grundy Coloring and Partial Grundy Coloring admit fixed-parameter tractable (FPT) algorithms, algorithms with running time $f(k)n^{{\mathcal{O}}(1)}$ , where $k$ is the number of colors, was posed as an open problem by Zaker and by Effantin et al., respectively.

Recently, Aboulker et al. (STACS 2020 and Algorithmica 2022) resolved the question for Grundy Coloring in the negative by showing that the problem is W[1]-hard. For Partial Grundy Coloring, they obtain an FPT algorithm on graphs that do not contain $K_{i,j}$ as a subgraph (a.k.a. $K_{i,j}$ -free graphs). Aboulker et al. re-iterate the question of whether there exists an FPT algorithm for Partial Grundy Coloring on general graphs and also asks whether Grundy Coloring admits an FPT algorithm on $K_{i,j}$ -free graphs. We give FPT algorithms for Partial Grundy Coloring on general graphs and for Grundy Coloring on $K_{i,j}$ -free graphs, resolving both the questions in the affirmative. We believe that our new structural theorems for partial Grundy coloring and “representative-family” like sets for $K_{i,j}$ -free graphs that we use in obtaining our results may have wider algorithmic applications.

Keywords and phrases:

Grundy Coloring, Partial Grundy Coloring, FPT Algorithm,

K_{i,j}

-free graphs

Funding:

Akanksha Agrawal: Supported by the New Faculty Seed Grant, IIT Madras
(No. NFSC008972).

Saket Saurabh: Supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 819416).

Copyright and License:

© Akanksha Agrawal, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and
Shaily Verma; licensed under Creative Commons License CC-BY 4.0

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Fixed parameter tractability

Editors:

Olaf Beyersdorff, Michał Pilipczuk, Elaine Pimentel, and Nguyễn Kim Thắng

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

A proper coloring of a graph $G$ is an assignment of colors to its vertices such that none of the edges have endpoints of the same color. In $k$ -Coloring, we are given a graph $G$ , and the objective is to test whether $G$ admits a proper coloring using at most $k$ colors. The $k$ -Coloring problem is one of the classical NP-hard problems, and it is NP-complete for every fixed $k\geq 3$ . The problem is notoriously hard even to approximate. Indeed, approximating $k$ -Coloring within $\operatorname{\mathcal{O}}(n^{1-\epsilon})$ , for any $\epsilon>0$ , is hard [18]. Also, under a variant of Unique Games Conjecture, there is no constant factor approximation for $3$ -Coloring [14].

The $k$ -Coloring problem has varied applications ranging from scheduling, register allocations, pattern matching, and beyond [8, 9, 29]. Owing to this, several heuristics-based algorithms have been developed for the problem. One of the most natural greedy strategies considers the vertices of an input graph $G$ in an arbitrary order and assigns to each vertex the first available color in the palette (the color palette for us is $\mathbb{N}$ ). In literature, this is called the first-fit rule. Notice that there is nothing special about using the “first” available color; one may instead opt for any of the previously used colors, if available, before using a new color; let us call this greedy rule the any-available rule. It leads to yet another greedy strategy to properly color a graph, and one can easily prove that this greedy strategy is equivalent to the “last-(available) fit” rule.

For any greedy strategy, one may wonder: How bad can the strategy perform for the given instance? The above leads us to the well-studied fundamental combinatorial problems, Grundy Coloring and Partial Grundy Coloring, that arise from the aforementioned greedy strategies for proper coloring. In the Grundy Coloring problem, we are given a graph $G$ on $n$ vertices and an integer $k$ , and the goal is to check if there is an ordering of the vertices on which the first-fit greedy algorithm for proper coloring uses at least $k$ colors. Similarly, we can define the Partial Grundy Coloring problem, where the objective is to check if, for the given graph $G$ on $n$ vertices and integer $k$ , there is an ordering of the vertices on which the any-available greedy algorithm uses at least $k$ colors. In this paper, we consider these two problems in the realm of parameterized complexity.

The Grundy Coloring problem has a rich history dating back to 1939 [21]. Goyal and Vishwanathan [20] proved that Grundy Coloring is NP-hard. Since then, there has been a flurry of results on the computational and combinatorial aspects of the problem both on general graphs and on restricted graph classes, see, for instance [6, 7, 16, 23, 26, 10, 36, 33, 37, 39, 35, 3, 27, 24, 38] (this list is only illustrative, not comprehensive). The problem Partial Grundy Coloring was introduced by Erdös et al. [16] and was first shown to be NP-hard by Shi et al. [34]. The problem has gained quite some attention thereafter; see, for instance [1, 32, 25, 36, 12, 15, 5, 4].

These problems have also been extensively studied from the parameterized complexity perspective. Unlike $k$ -Coloring, both these problems admit XP algorithms [38, 15], i.e., an algorithm running in time bounded by $|V(G)|^{f(k)}$ . The above naturally raises the question of whether they are fixed-parameter tractable (FPT), i.e., admit an algorithm running in time $f(k)\cdot|V(G)|^{\operatorname{\mathcal{O}}(1)}$ . In fact, these problems have also been explicitly stated as open problems [1, 7, 23, 33].

Havet and Sampaio [23] studied Grundy Coloring with an alternate parameter and showed that the problem of testing whether there is a Grundy coloring with at least $|V(G)|-q$ colors is FPT parameterized by $q$ . Bonnet et al. [7] initiated a systematic study of designing parameterized and exact exponential time algorithms for Grundy Coloring and obtained FPT algorithms for the problem for several structured graph classes. They gave an exact algorithm for Grundy Coloring running in time $2.443^{n}\cdot n^{\operatorname{\mathcal{O}}(1)}$ and also showed that the problem is FPT on chordal graphs, claw-free graphs and graphs excluding a fixed minor. In the same paper, they stated the tractability status of Grundy Coloring on general graphs parameterized by the treewidth or the number of colors as central open questions. Belmonte et al. [6] resolved the first question by proving that Grundy Coloring is W[1]-hard parameterized by treewidth, but surprisingly, it becomes FPT parameterized by pathwidth. Later, Aboulker et al. [1] proved that Grundy Coloring does not admit an FPT algorithm (parameterized by the number of colors) and obtained an FPT algorithm for Partial Grundy Coloring on $K_{t,t}$ -free graphs (which includes graphs of bounded degeneracy, graphs excluding some fixed graph as minor/topological minors, graphs of bounded expansion and nowhere dense graphs). A graph is $K_{i,j}$ -free if it does not have a subgraph isomorphic to the complete bipartite graph with $i$ and $j$ vertices, respectively, on the two sides. They concluded their work with the following natural open questions:

Question 1:: Does Partial Grundy Coloring admit an FPT algorithm?
Question 2:: Does Grundy Coloring admit an FPT algorithm on $K_{i,j}$ -free graphs?

In this paper, we resolve the questions $1$ and $2$ in the affirmative by a new structural result and a new notion of representative families for $K_{i,j}$ -free graphs, respectively. In the next section, we give an intuitive overview of both results, highlighting our difficulties and our approaches to overcome them.

1.1 Our Results, Methods and Overview

Our first result is the following.

Theorem 1.

Partial Grundy Coloring is solvable in time $2^{{\mathcal{O}}(k^{5})}\cdot n^{{\mathcal{O}}(1)}$ .

Our algorithm starts with the known “witness reformulation” of Partial Grundy Coloring. It is known that $(G,k)$ is a yes-instance of Partial Grundy Coloring if and only if there is a vertex subset $W$ of size at most $k^{2}$ such that, $(G[W],k)$ is a yes-instance of the problem. In the above, the set $W$ is known as a small witness set. Our algorithm is about finding such a set $W$ of size at most $k^{2}$ . Observe that this witness reformulation immediately implies that Partial Grundy Coloring admits an algorithm with running time $n^{{\mathcal{O}}(k^{2})}$ time. To build our intuition, we first give a simple algorithm for the problem on graphs of bounded degeneracy (or even, nowhere dense graphs). This algorithm has two main steps: (a) classical color-coding of Alon-Yuster-Zwick [2], and (b) independence covering lemma of Lokshtanov et al. [28].

Let $(G,k)$ be a yes instance of Partial Grundy Coloring, where $G$ is a $d$ -degenerate graph on $n$ vertices, and $W$ be a small witness set of size at most $k^{2}$ . As $(G[W],k)$ must be a yes-instance of the problem, there exists an ordering of the vertices such that when we apply any-available greedy rule, it uses at least $k$ colors. Let $\widehat{c}$ be this proper coloring of $G[W]$ . The tuple $(W_{i}:=\{v\in W\mid\widehat{c}(v)=i\})_{i\in[k]}$ is called a $k$ -partial Grundy witness for $G$ . Now we apply the color-coding step of the algorithm. That is, we color the vertices of $G$ using $k$ colors independently and uniformly at random, and let $Z_{1},\cdots,Z_{k}$ be the color classes of this coloring. The probability that for each $i\in[k]$ , $W_{i}\subseteq Z_{i}$ , is $k^{-k^{2}}$ . Notice that since $G$ is a $d$ -degenerate graph, we have that $G_{i}=G[Z_{i}]$ , for each $i\in[k]$ , is $d$ -degenerate. Now we exploit this fact and apply the independence covering lemma of Lokshtanov et al. [28]. That is given as input $(G_{i},k^{2})$ , in time $2^{{\mathcal{O}}(dk^{2})}n^{{\mathcal{O}}(1)}$ it produces a family ${\mathcal{F}}_{i}$ of independent sets of $G_{i}$ , of size $2^{{\mathcal{O}}(dk^{2})}\cdot\log n$ . Furthermore, given any independent set $I$ of $G_{i}$ of size at most $k^{2}$ , there exists an independent set $F\in{\mathcal{F}}_{i}$ , such that $I\subseteq F$ ( $F$ covers $I$ ). In particular, we know that there is a set $F_{i}\in{\mathcal{F}}_{i}$ that covers $W_{i}$ . So, the algorithm just enumerates each tuple $(F_{1},\ldots,F_{k})$ of ${\mathcal{F}}_{1}\times\cdots\times{\mathcal{F}}_{k}$ and checks whether $(F_{1},\cdots,F_{k})$ is a $k$ -partial Grundy coloring of $G[F_{1}\cup\cdots\cup F_{k}]$ . If $(G,k)$ is a yes instance, our algorithm is successful with probability $k^{-k^{2}}$ . Moreover, we can convert the described randomized algorithm to a deterministic one by using the standard derandomization technique of “universal sets” [31, 17]. Some remarks are in order; it can be shown that each of $|W_{i}|\leq k$ , and hence we can call the independence covering lemma on $(G_{i},k)$ , resulting in an improved running time of $2^{\operatorname{\mathcal{O}}(dk^{2}\log k)}\cdot n^{\operatorname{\mathcal{O}% }(1)}$ . Aboulker et al. [1] proved that Partial Grundy Coloring on $K_{t,t}$ -free graphs is FPT, which includes $t$ -degenerate graphs. Aboulker et al. did not explicitly mention the running time, but their running time is at least $2^{k^{t}}n$ . Our new algorithm improves over this. For general instances, we do not have a bound on the degeneracy of the input graph. However, we can achieve this by using our new structural result.

Theorem 2 (Structural result).

There is a polynomial-time algorithm that given a graph $G$ and a positive integer $k$ , does one of the following:

(i)

Correctly concludes that $(G,k)$ is a yes-instance of Partial Grundy Coloring, or
(ii)

Outputs at most $2k^{3}$ induced bicliques $A_{1},\cdots,A_{\ell}$ in $G$ such that the following holds. For any $v\in V(G)$ , the degree of $v$ in $G-F$ is at most $k^{3}$ , where $F$ is the union of the edges in the above bicliques.

The structural result (Theorem 2) is one of our main technical contributions. Next, we show how to design an algorithm for Partial Grundy Coloring using Theorem 2. We follow the same steps as for the one described for the degenerate case. That is, we have color classes $Z_{i}$ s and they contain the respective $W_{i}$ s (the part of the small witness set $W$ ). Now, to design a family of independent sets in $G_{i}=G[Z_{i}]$ , we do as follows. Let $(L_{j},R_{j})$ be a bipartition of $A_{j}$ , for each $j\in[\ell]$ . Observe that any independent set $I$ (in particular of $G_{i}$ ) intersects $L_{j}$ or $R_{j}$ , but not both, for any $j\in[\ell]$ . Thus, we first guess whether $W_{i}$ intersects $L_{j}$ , $R_{j}$ or none. Let this be given by a function $f_{i}:[\ell]\rightarrow\{L,R,N\}$ , that is, if $f_{i}(j)=L$ , then $W_{i}\cap L_{j}=\emptyset$ , if $f_{i}(j)=R$ , then $W_{i}\cap R_{j}=\emptyset$ , else $W_{i}\cap(L_{j}\cup R_{j})=\emptyset$ . Taking advantage of this property, for each guess of which of $L_{j}$ or $R_{j}$ is not contained in $W_{i}$ , we delete the corresponding set (which is one of $L_{j}$ or $R_{j}$ , for each $j\in[\ell]$ ) from $G_{i}$ . We call the resulting graph $G_{i}^{f_{i}}$ . This implies that for any $f_{i}$ , in $G_{i}^{f_{i}}$ we delete all edges of $F$ (where $F$ is the union of edges in the bicliques). Hence, the maximum degree of $G_{i}^{f_{i}}$ is at most $k^{3}$ , and therefore it has degeneracy at most $k^{3}$ . Now using the independence covering step of the algorithm for degenerate graphs, we can finish the algorithm. The proof of Theorem 2 is obtained by carefully analyzing the reason for the failure of a greedy algorithm.

Our next result is an affirmative answer to Question $2$ .

Theorem 3.

For any fixed $i,j\in\mathbb{N}$ , there is an FPT algorithm that given a graph $G$ and a positive integer $k$ , decides if there is Grundy coloring of $G$ using at least $k$ colors.

For our algorithm, we use a reinterpretation of the problem which is based on the existence of a small witness. Gyárfás et al. [22], and Zaker [38] independently showed that a given instance $(G,k)$ of Grundy Coloring is a yes-instance if and only if there is a vertex subset $W$ of size at most $2^{k-1}$ , such that $(G[W],k)$ is also a yes-instance of the problem. The existence of this small induced subgraph directly yield an XP algorithm for the problem [38]. Using characterizations of [22, 38] and basic Grundy coloring properties, we can reduce Grundy Coloring to finding a homomorphic image, satisfying some independence constraints, of some specific labeled trees (see Fig. 1, where different parts of it will be discussed, shortly). Let the pair $(T,\ell)$ denote a rooted tree $T$ together with a labeling function $\ell:V(T)\rightarrow[k]$ . Given $(T,\ell)$ and a graph $G$ , a function $\omega:V(T)\rightarrow V(G)$ is a labeled homomorphism if: i) for each $\{u,v\}\in E(T)$ , we have $\{\omega(u),\omega(v)\}\in E(G)$ , and ii) for $u,v\in V(T)$ , if $\ell(u)\neq\ell(v)$ , then $\omega(u)\neq\omega(v)$ . In particular, we will reduce the problem to the following.

Constrained Label Tree Homomorhism (CLTH) Parameter: $|V(T)|$ Input: A host graph $G$ and $(T,\ell:V(T)\rightarrow[k])$ , where $T$ is a tree. Question: Does there exists a labeled homomorphism $\omega:V(T)\rightarrow V(G)$ such that for any $z\in[k]$ , $W_{i}=\{\omega(t)\mid t\in V(T)\mbox{ and $\ell(t)=i$}\}$ is an independent set in $G$ ?

Figure 1: Illustration of a labelled homomorphism

\omega:V(T_{4})\rightarrow V(G)

, where the graph is shown in part (i),

T_{4}

with

V(T_{4})=\{r_{4},r_{4,3},r_{4,2},r_{4,1},r_{4,3,2},r_{4,3,1},r_{4,2,1}\}

is shown in part (ii), and a relation to Grundy coloring is illustrated in part (iii). Here,

\omega(r_{4})=v_{1}

,

\omega(r_{4,3})=v_{6}

,

\omega(r_{4,2})=v_{2},\omega(r_{4,1})=v_{3},\omega(r_{4,3,2})=v_{2},\omega(r_{% 4,3,1})=v_{3}

, and

\omega(r_{4,2,1})=v_{4}

.

Now our goal is to identify $\omega$ (and thus the witness set $W$ ). The first step of our algorithm will be to use the color-coding technique of Alon-Yuster-Zwick [2] to ensure that the labeling requirement of the graph homomorphism $\omega$ is satisfied. To this end, we randomly color the vertices of $G$ using $k$ colors, where we would like the random coloring to ensure that for each $z\in[k]$ , all the vertices in $W_{z}$ are assigned the color $z$ . Let $X_{1},X_{2},\cdots,X_{k}$ be the color classes in a coloring that achieves the above property. Our objective will be to find $\omega$ such that vertices of $T$ that are labeled $z\in[k]$ are assigned to vertices in $X_{z}$ .

Our next challenge is to find a homomorphism that additionally satisfies the independence condition. That is, vertices of the same label in $T$ are assigned to an independent set in $G$ . Note that the number of potential $\omega$ s that satisfy our requirements can be very huge; however, we will be able to carefully exploit $K_{i,j}$ -freeness to design a dynamic programming-based algorithm to identify one such $\omega$ (and thus the set $W$ ). Our approach here is inspired by dynamic programming in the design of FPT algorithms based on computations of “representative sets” [30, 19]. However, this inspiration ends here, as to apply known methods we need to have an underlying family of sets that form a matroid. Unfortunately, we do not have any matroid structure to apply the known technique. Here, we exploit the fact that we have a specific labeled tree $(T,\ell)$ and a $K_{i,j}$ -free graph. Next we define the specific trees that we will be interested in (see Fig. 1, (ii)).

Definition 4.

For each $k\in\mathbb{N}\setminus\{0\}$ , we (recursively) define a pair $(T_{k},\ell_{k}:V(T_{k})\rightarrow[k])$ , called a $k$ -Grundy tree, where $T_{k}$ is a tree and $\ell_{k}$ is a labelling of $V(T_{k})$ , as follows :

1.

$T_{1}=(\{r_{1}\},\emptyset)$ is a tree with exactly one vertex $r_{1}$ (which is also its root), and $\ell_{1}(r_{1})=1$ .
2.

Consider any $k\geq 2$ , we (recursively) obtain $T_{k}$ as follows. For each $z\in[k-1]$ , let $(T_{z},\ell_{z})$ be the $z$ -Grundy tree with root $r_{z}$ . We assume that for distinct $z,z^{\prime}\in[k-1]$ , $T_{z}$ and $T_{z^{\prime}}$ have no vertex in common, which we can ensure by renaming the vertices.¹¹1For the sake of notational simplicity we will not explicitly write the renaming of vertices used to ensure pairwise vertex disjointness of the trees. This convention will be followed in the relevant section. We set $V(T_{k})=\big{(}\cup_{z\in[k-1]}V(T_{z})\big{)}\cup\{r_{k}\}$ and $A(T_{k})=\big{(}\cup_{z\in[k-1]}A(T_{z})\big{)}\cup\{(r_{k},r_{z})\mid z\in[k-% 1]\}$ . We set $\ell_{k}(r_{k})=k$ , and for each $z\in[k-1]$ and $t\in V(T_{z})$ , we set $\ell_{k}(t)=\ell_{z}(t)$ .

For $v\in V(T_{k})$ , $\ell_{k}(v)$ is the label of $v$ in $(T_{k},\ell_{k})$ , and the elements in $[k]$ are labels of $T_{k}$ .

Observe that the label of a vertex $t\in V(T)$ is the depth of the subtree rooted at $t$ (the depth of a leaf is $1$ ). In particular, the leaves are assigned the label $1$ , and when they are deleted, we get vertices with the label $2$ as leaves, and so on. This allows us to do a bottom-up dynamic programming over $T_{k}$ . Roughly speaking, for each $z\in[k]$ , we solve the special labelled tree homomorphism from $\omega_{z}:V(T_{z})\rightarrow X_{1}\cup X_{2}\ldots\cup X_{z}$ , where the root of $T_{z}$ is mapped to a fixed vertex $v\in X_{z}$ as follows: instead of having all potential choices for $\omega_{z}$ (or $W_{z}=\{\omega_{z}(t)\mid t\in V(T_{z})\}$ ), we find enough representatives, that will allow us to replace $W_{z}$ by something that we have stored. It is a priori not clear that such representative sets of small size exist and furthermore, even if they exist, how to find them. The existence and computation of small representative sets in this setting is our main technical contribution for Grundy Coloring.

We heavily exploit the $K_{i,j}$ -freeness in our “representative set” computation. Very roughly stating, while we have computed required representatives for $W_{z}$ , and wish to build such a representatives for $W_{z+1}$ , by exploiting $K_{i,j}$ -freeness, we either find a small hitting set or a large sub-family of pair-wise disjoint sets. In the former case, we can split the family and focus on the subfamily containing a particular vertex from the hitting set and obtain a “representative” for it (and then take the union over such families). In the latter case, we show that we are very close to satisfying the required property, except for the sets containing vertices from an appropriately constructed small set $S$ of vertices. The construction of this small set $S$ is crucially based on the $K_{i,j}$ -freeness of the input graph. Once we have the set $S$ , we can focus on sets containing a vertex from it and compute “representatives” for them.

Again, using standard hash functions, we can obtain a deterministic FPT algorithm for the problem by derandomizing the color coding based step [2, 31].

2 Preliminaries

Generic Notations.

We denote the set of natural numbers by $\mathbb{N}$ . For $n\in\mathbb{N}$ , $[n]$ denotes the set $\{1,2,\cdots,n\}$ . For a function $f:X\rightarrow Y$ and $y\in Y$ , $f^{-1}(y):=\{x\in X\mid f(x)=y\}$ .

For standard graph notations not explicitly stated here, we refer to the textbook of Diestel [13]. For a graph $G$ , we denote its vertex and edge set by $V(G)$ and $E(G)$ , respectively. Also, if the context is clear, we will use $n$ and $m$ to denote the numbers $|V(G)|$ and $|E(G)|$ , respectively. The neighborhood of a vertex $v$ in a graph $G$ is the set of vertices that are adjacent to $v$ in $G$ , and we denote it by $N_{G}(v)$ . The degree of a vertex $v$ is the size of its neighborhood in $G$ , and we denote it by $d_{G}(v)$ . For a set of vertices $S\subseteq V(G)$ , we define $N_{G}(S)=(\cup_{v\in S}N(v))\setminus S$ . When the graph is clear from the context, we drop the subscript $G$ from the above notations. For $X\subseteq V(G)$ , the induced subgraph of $G$ on $X$ , denoted by $G[X]$ , is the graph with vertex set $X$ and edge set $\{\{u,v\}\mid u,v\in X\ \&\ \{u,v\}\in E(G)\}$ . Also, $G[V(G)\setminus X]$ is denoted by $G-X$ . For $v\in V(G)$ , we use $G-v$ to denote $G-\{v\}$ for ease of notation. For an edge subset $F\subseteq E(G)$ , $G-F$ is the graph with vertex set $V(G)$ and edge set $E(G)\setminus F$ . A bipartite graph $G=(A\uplus B,E)$ is called a biclique if every vertex in $A$ is adjacent to every vertex in $B$ . We assume that $A$ and $B$ are both non-empty sets. For $d\in\mathbb{N}$ , a graph is $d$ -degenerate if each of its subgraphs has a vertex of degree at most $d$ . For terminologies related to parameterized complexity, see the textbook of Cygan et al. [11].

3 FPT Algorithm for Partial Grundy Coloring

Consider a graph $G$ and an integer $k\in\mathbb{N}\setminus\{0\}$ . For a (not necessarily proper) coloring $\chi:V(G)\rightarrow[k]$ , for simplicity, we sometimes write $\chi$ as the ordered tuple $(\chi^{-1}(1),\chi^{-1}(2),\cdots,$ $\chi^{-1}(k))$ . Recall that a proper coloring of a graph is a coloring of its vertices so that for none of its edges, the two endpoints of it are of the same color. Also, a $k$ -partial Grundy coloring of $G$ is a proper coloring $c:V(G)\rightarrow[k]$ , such that for each $i\in[k]$ , there is a vertex $v\in V(G)$ with: $(i)$ $c(v)=i$ and $(ii)$ for every $j\in[i-1]$ , there is $u\in N_{G}(v)$ with $c(u)=j$ .

We will begin with some definitions and results that will be useful in obtaining our main structural result (Theorem 2) and our FPT-algorithm (Theorem 1).

Observe that given a $k$ -partial Grundy coloring of an induced subgraph $\widehat{G}$ of a graph $G$ , we can extend this coloring to a partial Grundy coloring of the whole graph $G$ using at least $k$ colors by greedily coloring the uncolored vertices of $G-V(\widehat{G})$ . The following observation will be particularly useful when we work with a small “witness”.

Observation 5.

Given a graph $G$ , an induced subgraph $\widehat{G}$ of $G$ , and a partial Grundy coloring of $\widehat{G}$ using $k$ colors, we can find a partial Grundy coloring of $G$ using at least $k$ colors in linear time.

Proof.

Let $\widehat{c}:V(\widehat{G})\rightarrow[k]$ be a partial Grundy coloring of $\widehat{G}$ with exactly $k$ colors. We construct a partial Grundy coloring $c:V(G)\rightarrow\mathbb{N}$ of $G$ using at least $k$ colors as follows. For each vertex $v\in V(\widehat{G})$ , set $c(v):=\widehat{c}(v)$ . Let $v_{1},v_{2},\cdots,v_{n^{\prime}}$ be an arbitrarily fixed order of vertices in $V(G)\setminus V(\widehat{G})$ . Let $G_{0}=\widehat{G}$ , and for each $p\in[n^{\prime}]$ , $G_{p}=G[V(\widehat{G}\cup\{v_{1},v_{2},\cdots,v_{p}\})]$ . We iteratively create a partial Grundy coloring $c_{p}$ of $G_{p}$ using at least $k$ colors (in increasing values of $p$ ) as follows. Note that $c_{0}=\widehat{c}$ is already a partial Grundy coloring of $G_{0}$ that uses at least $k$ colors. Consider $p\in[n^{\prime}]\setminus\{0\}$ , and assume that we have already computed a partial Grundy coloring $c_{p-1}:V(G_{p-1})\rightarrow\mathbb{N}$ of $G_{p-1}$ that uses $k^{\prime}\geq k$ colors. For each $z\in[k^{\prime}]$ , let $V_{z}=c_{p-1}^{-1}(z)$ . For each $v\in V(G_{p-1})$ , we set $c_{p}(v):=c_{p-1}(v)$ . If the vertex $v_{p}$ has a neighbor in each of the sets $V_{1},V_{2},\cdots,V_{k^{\prime}}$ , i.e., if for each $z\in[k^{\prime}]$ , $N_{G}(v_{p})\cap V_{z}\neq\emptyset$ , then set $c_{p}(v_{p}):=k^{\prime}+1$ . Otherwise, let $z^{*}\in[k^{\prime}]$ be the smallest number such that $N_{G}(v_{p})\cap V_{z^{*}}=\emptyset$ , and set $c_{p}(v_{p}):=z^{*}$ . Notice that by construction, $c_{p}$ is a partial Grundy coloring of $G_{p}$ using at least $k$ colors. From the above discussions, $c_{n^{\prime}}$ is a partial Grundy coloring of $G=G_{n^{\prime}}$ using at least $k$ colors. $\hfill\blacktriangleleft$

Definition 6.

Consider a graph $G$ and an integer $k\in\mathbb{N}\setminus\{0\}$ . A sequence of pairwise disjoint independent sets $(Q_{1},Q_{2},\ldots,Q_{k})$ of $G$ is a $k$ -partial Grundy witness if the following holds. For any $i\in[k]$ , there is $v\in Q_{i}$ such that for all $j\in[i-1]$ , $Q_{j}\cap N_{G}(v)\neq\emptyset$ . The vertex $v$ is called a dominator in $Q_{i}$ .

Observation 7.

Given a graph $G$ and an integer $k$ , let $(Q_{1},Q_{2},\ldots,Q_{k})$ be a $k$ -partial Grundy witness. Suppose $Y_{1},Y_{2},\ldots,Y_{k}$ are pairwise disjoint independent sets in $G$ such that $Q_{i}\subseteq Y_{i}$ , for all $i\in[k]$ . Then $(Y_{1},Y_{2},\ldots,Y_{k})$ is also a $k$ -partial Grundy witness of $G$ .

A $k$ -partial Grundy witness $(X_{1},X_{2},\ldots,X_{k})$ is small if for each $i\in[k]$ , $|X_{i}|\leq k-i+1$ . Next, we prove the existence of a small $k$ -partial Grundy witness. This result is the same as the one obtained by Effantin et al. [15]; however, it is stated slightly differently for convenience.

Observation 8 ( $\spadesuit$ ).

²²2The proofs of the result marked with $\spadesuit$ can be found in the full version of the paper on arXiv. Let $G$ be a graph and $k$ be an integer, where $G$ has a $k$ -partial Grundy witness $(Q_{1},\ldots,Q_{k})$ . Then, there exists a $k$ -partial Grundy witness $(X_{1},X_{2},\ldots,X_{k})$ such that for each $i\in[k]$ , $X_{i}\subseteq Q_{i}$ and $|X_{i}|\leq k-i+1$ .

The remainder of this section is organized as follows. In Section 3.1 we prove our key structural result (Theorem 2), and then obtain our algorithm in Section 3.2. (Readers who may want to read the algorithm directly, may skip Section 3.1.)

3.1 Degree Reduction: Proof of Theorem 2

The objective of this section is to prove Theorem 2. The proof of this theorem is based on the following lemma for bipartite graphs.

Lemma 9.

There is a polynomial-time algorithm that, given a bipartite graph $G=(A\uplus B,E)$ and a positive integer $k$ , does one of the following.

(i)

Correctly concludes that the partial Grundy coloring of $G$ is at least $k$ .
(ii)

Outputs at most $4k-4$ bicliques $A_{1},\cdots,A_{\ell}$ in $G$ such that for any $v\in V(G)$ , degree of $v$ in $G-F$ is at most $k^{2}$ , where $F$ is the union of the edges in the above bicliques.

We first give a proof of Theorem 2 based on the above lemma.

Proof of Theorem 2.

Consider a graph $G$ and a positive integer $k$ . First, we run the first-fit greedy algorithm for proper coloring of the graph $G$ for an arbitrarily fixed ordering $(v_{1},v_{2},\cdots,v_{n})$ of $V(G)$ . For each $j$ , let $C_{j}$ be the vertices colored $j$ and $k^{\prime}$ be the largest integer such that $C_{k^{\prime}}\neq\emptyset$ . Note that $(C_{1},\cdots,C_{k^{\prime}})$ is a proper coloring of $G$ . Also, for any $j\in[k^{\prime}]$ and any vertex $v$ in $C_{j}$ , $v$ has a neighbor in $C_{j^{\prime}}$ for all $j^{\prime}\in[j-1]$ . If $k^{\prime}\geq k$ , then $(C_{1},\cdots,C_{k^{\prime}})$ is a partial Grundy coloring of $G$ using at least $k$ colors, and thus we can correctly report it.

Next, we assume that $k^{\prime}<k$ . Note that all the edges in $G$ are between the color classes $C_{1},\cdots,C_{k^{\prime}}$ . Now for every distinct $i,j\in[k^{\prime}]$ , where $i<j$ , we apply Lemma 9 on $(H_{i,j}=(C_{i}\uplus C_{j},E(C_{i},C_{j})),k)$ , where $E(C_{i},C_{j})$ is the set of edges in $G$ between the color classes $C_{i}$ and $C_{j}$ . Our algorithm will declare that $G$ has a partial Grundy coloring using at least $k$ colors if we get the output given in statement $(i)$ in any of the $\binom{k^{\prime}}{2}$ applications of Lemma 9. Otherwise, for every distinct $i,j\in[k^{\prime}]$ , where $i<j$ , let $A_{i,j,1},\cdots,A_{i,j,\ell_{i,j}}$ be the bicliques, we get as output by the algorithm in Lemma 9 on $(H_{i,j}$ $,k)$ . Note that $\ell_{i,j}\leq 4k-4$ . Now our algorithm will output the bicliques $\{A_{i,j,r}\leavevmode\nobreak\ \colon\leavevmode\nobreak\ 1\leq i<j\leq k^{% \prime},r\in[\ell_{i,j}]\}$ . As $k^{\prime}<k$ for all $1\leq i<j\leq k^{\prime}$ , the number of bicliques we output is at most $(4k-4)\binom{k^{\prime}}{2}$ , that is, at most $2k^{3}$ . Since any vertex in a color class $C_{r}$ has neighbors in other color classes, for $r\in[k^{\prime}]$ and we applied Lemma 9 for every pair of color classes, the degree of $v$ in $G-F$ is at most $k^{3}$ for any $v\in V(G)$ , where $F$ is the union of the edges in the above bicliques. This completes the proof of the theorem. $\hfill\blacktriangleleft$

We now focus on the proof of Lemma 9. Toward this, we give a polynomial time procedure that, given a bipartite graph $G=(L\uplus R,E)$ and a positive integer $k$ , either concludes that the input graph has partial Grundy coloring using at least $k$ colors or it outputs at most $2k-2$ bicliques $A_{1},\ldots,A_{\ell}$ in $G$ such that for any $v\in L$ , $d_{G-F}(v)\leq k^{2}$ , where $F$ is the union of the edges in the above bicliques. That is, removal of the edges of these bicliques bounds the degree of each vertex in $L$ by $k^{2}$ . We get the proof of Lemma 9 by applying this algorithm once for $L$ and then for $R$ .

Overview of our algorithm.

Let $\sigma=v_{1},v_{2},\ldots,v_{n}$ be an ordering of the vertices in $L$ in non-increasing order of their degree in $G$ . The algorithm constructs specific color classes $Q_{1},Q_{2},\ldots,Q_{r}$ in this order so that $(C_{1}=Q_{r},C_{2}=Q_{r-1},\ldots,C_{r}=Q_{1})$ is an $r$ -partial Grundy witness, where $|Q_{j}|\leq j$ . Furthermore, we will construct sets $B_{i}$ , $i\in[r]$ , which will be used to construct the bicliques. Notice that if we obtain $r\geq k$ , then we will be able to conclude that $G$ has a partial Grundy coloring using at least $k$ colors. Let $Q_{1}=\{v_{1}\}$ and in our construction $v_{1}$ will be the dominator in $Q_{1}$ (and our construction needs to ensure this property; see Definition 6). Consider the construction of $Q_{2}$ . Let $i$ be the smallest index in $\{2,3,\ldots,n\}$ for which there is a vertex $w\in N_{G}(v_{1})$ such that $v_{i}$ is not adjacent to $w$ . Then, we set $Q_{2}=\{v_{i},w\}$ , and designate $v_{i}$ as the dominator in color class $C_{r-1}=Q_{2}$ . Notice that all the vertices in $B_{1}=\{v_{2},\ldots,v_{i-1}\}$ are adjacent to all the vertices in $N_{G}(v_{1})$ , and hence they together form a biclique (with bipartition $B_{1}$ and $N_{G}(v_{1})$ ). This property will be extended in building each $Q_{j}$ s and the required bicliques.

For the construction of $Q_{j}$ , we consider unprocessed vertices (i.e., the vertices that do not belong to the previously constructed sets, i.e., to $Q_{1}\cup B_{1}\cup\ldots\cup Q_{j-1}\cup B_{j-1}$ ) as follows. We would now like to choose an unprocessed vertex $v_{i^{\prime}}$ , so that we can make $v_{i^{\prime}}$ the dominator of $Q_{j}$ , and additionally, for each $j^{\prime}\in[j-1]$ , we can include a neighbor of the dominator from $Q_{j^{\prime}}$ to the set $Q_{j}$ . Note for us to do the above, we need to ensure that the vertices that we add to $Q_{j}$ is an independent set in $G$ , and all the vertices that we want to include in the set $Q_{j}$ are outside $Q_{1}\cup\ldots\cup Q_{j-1}$ . That is, among the unprocessed vertices, we choose the first vertex $v_{i^{\prime}}$ with the following property: for each $j^{\prime}\in[j-1]$ , we have a neighbor $w_{j^{\prime}}$ of the previously constructed dominator in $Q_{j^{\prime}}$ such that $w_{j^{\prime}}\notin Q_{1}\cup\ldots\cup Q_{j-1}$ and $(v_{i^{\prime}},w_{j^{\prime}})\notin E(G)$ ; we set $Q_{j}=\{v_{i^{\prime}},w_{1},\ldots,w_{j-1}\}$ . We would like to mention that all the dominators we construct are from the bipartition $L$ and hence $\{w_{1},\ldots,w_{j-1}\}\subseteq R$ . This will imply that $Q_{j}$ is an independent set.

Moreover, by the choice of $v_{i^{\prime}}$ as the smallest vertex with the desired property, it follows that for any vertex $v_{r}$ that appears before $v_{i^{\prime}}$ in the order $\sigma$ and $v_{r}\notin P=Q_{1}\cup\ldots\cup Q_{j-1}$ , the vertex $v_{r}$ is adjacent to all the vertices in $N(x_{j^{\prime}})\setminus P$ , where $x_{j^{\prime}}$ is the dominator in $Q_{j^{\prime}}$ , for some $j^{\prime}\in[j-1]$ . Then we add $v_{r}$ to $B_{j^{\prime}}$ . Note that in the above process, we still maintain the biclique property, by explicitly ensuing that $B_{j^{\prime}}$ and $N(x_{j^{\prime}})\setminus(Q_{1}\cup\ldots\cup Q_{j-1}\cup Q_{j})$ forms a biclique.

Description of the algorithm.

We give a pseudocode of our algorithm in Algorithm 1. First, the algorithm intializes the sets $B_{i}$ and $Q_{i}$ to be the empty set, for all $i\in[k]$ (see Algorithm 1). Let $\sigma=v_{1},v_{2},\ldots,v_{n}$ be an ordering of the vertex set $L$ in the non-increasing order of their degrees. Now, we want to construct the color classes $Q_{1},Q_{2},\ldots,Q_{k}$ , iteratively, such that $(C_{1},C_{2},\ldots,C_{k})=(Q_{k},Q_{k-1},\ldots,Q_{1})$ is a $k$ -partial Grundy witness. At line 3, we intialize with $Q_{1}:=\{v_{1}\}$ , $x_{1}:=v_{1}$ , and fix the index $q=2$ . Here, $Q_{1}$ will be the color class $C_{k}$ with dominator vertex $x_{1}$ . Now consider an iteration of the while loop. The algorithm checks if the set $L\setminus\big{(}\bigcup_{j\in[q-1]}(Q_{j}\cup B_{j})\big{)}$ is non-empty and executes the while loop. At this point we have constructed sets $Q_{1},\ldots,Q_{q-1}$ such that $(Q_{q-1},Q_{q-2},\ldots,Q_{1})$ is a $(q-1)$ -partial Grundy witness such that each $x_{i}$ is a dominator vertex in $Q_{i}$ . Let $v_{r}$ be the first unprocessed vertex in $L$ and $P=\cup_{j\in[q-1]}Q_{j}$ by Lines 5 and 6. Now, we check if we can construct the current color class $Q_{q}$ with vertex $v_{r}$ as a dominator vertex, and for that, we need to add a neighbor $w_{j}$ (which is not added to any $Q_{i^{\prime}}$ before) for each already discovered dominator $x_{j}$ such that $w_{j}$ is non-adjacent to $v_{r}$ . Now, if there exists some $j\in[q-1]$ such that each neighbor of $x_{j}$ is a neighbor of $v_{r}$ , then we will not be able to construct $Q_{q}$ with vertex $v_{r}$ in it. In that case, we choose such a value $j$ and add $v_{r}$ to $B_{j}$ (See Line 8). Here, notice that $v_{r}$ is adjacent to all the vertices $N({x_{j}})\setminus P$ . We will maintain this property for all the vertices added to $B_{j}$ , i.e., $B_{j}$ union $N({x_{j}})\setminus\bigcup_{i}Q_{i}$ forms a biclique. Now consider the case that the condition in the if statement in Line 7 is false. Then, we choose a vertex $w_{j}\in N(x_{j})\setminus(P\cup N(v_{r}))$ for each $j\in[q-1]$ , by line 11 and set the vertex $v_{r}$ as the dominator for $Q_{q}$ , that is, $Q_{q}:=\{x_{q}\}\cup\{w_{1},\cdots,w_{q-1}\}$ , at Line 13. Notice that $Q_{q}$ is an independent set because there is no edge between $x_{1}$ and a vertex in $\{w_{1},\ldots,w_{q-1}\}$ , and $\{w_{1},\ldots,w_{q-1}\}$ is a subset of $R$ , the right part of the bipartition of $G$ . We repeat the iteration until one of the while loop conditions at line 4 fails. Next, if $q\geq k+1$ , we conclude that $G$ has a partial Grundy coloring using $k$ colors by line 18, because $(Q_{q-1},\ldots,Q_{1})$ is a $(q-1)$ -partial Grundy witness, where $q-1\geq k$ . Otherwise, by line 20, let $A_{j}$ be the graph induced on $B_{j}\cup(N(x_{j})\setminus P)$ and $S_{j}$ be the graph induced on $N[x_{j}]$ , for each $j\in[q-1]$ . Recall that $A_{j}$ is a biclique. It is easy to see that $S_{j}$ is a biclique, because $G$ is a bipartite graph. At line 21, the algorithm outputs the set of graphs $A_{1},\cdots,A_{q-1}$ and $S_{1},\cdots,S_{q-1}$ .

Algorithm 1 Algorithm for one-sided bipartite structural result.

The number of iterations of the while loop is at most $n$ and each step in the algorithm takes polynomial time, the total running time of the algorithm is polynomial in the input size. Next, we prove the correctness of the algorithm.

Lemma 10.

Algorithm 1 is correct.

Proof.

Let $q^{\star}$ be the value of $q$ at the end of the algorithm. To prove the correctness of the algorithm, first, we prove the following claim.

Claim 11.

The following statements are true.

(i)

For each $i\in[q^{\star}-1]$ , $Q_{i}$ is an independent set and $Q_{i}\neq\emptyset$ .
(ii)

For each $i\in[q^{\star}-1]$ and $j\in[i-1]$ , $N(x_{j})\cap Q_{i}\neq\emptyset$ .
(iii)

For each $i\in[q^{\star}-1]$ and $v\in B_{i}$ , $v$ is adjacent to all the vertices in $N(x_{i})\setminus(\bigcup_{j\in[q^{\star}-1]}Q_{j})$ and $d_{G}(v)\leq d_{G}(x_{i})$ .

Proof.

We prove the statements by induction on $i$ . The base case is when $i=1$ . Clearly, $Q_{1}=\{x_{1}\}$ and hence statement (i) is true. Statement (ii) is vacuously true. Next, we prove statement (iii). Notice that in any iteration of the while loop, in Step 8, we may add a vertex $v_{r}$ to $B_{1}$ . If this happens, then we know that $N(x_{1})\subseteq P\cup N(v_{r})$ , where $P$ is a subset of $\bigcup_{j\in[q^{\star}-1]}Q_{j}$ . That is, all the vertices in $N(x_{1})\setminus P$ are adjacent to $v_{r}$ . This implies that $v_{r}$ is adjacent to all the vertices in $N(x_{1})\setminus(\bigcup_{j\in[q^{\star}-1]}Q_{j})$ . Since $x_{1}$ is the vertex with the maximum degree, we have that $d_{G}(v_{r})\leq d(x_{1})$ .

Next, for the induction step, we assume that the induction hypothesis is true for $i-1$ , and we will prove that the hypothesis is true for $i$ . Consider the iteration $h^{\star}$ of the while loop when $q=i$ and Steps 11-14 is executed. Let $v_{r}$ be the vertex mentioned in Step 5 during that iteration. The vertices $w_{1},\cdots,w_{q-1}$ belongs to $R$ (the right side of the bipartition of $G$ ) and hence $\{w_{1},\cdots,w_{q-1}\}$ is an independent set. Also, notice that each $w_{j}$ does not belong to $N(v_{r})$ (See Step 11). Hence, $Q_{q}:=\{v_{r}\}\cup\{w_{1},\cdots,w_{q-1}\}$ is an independent set and $Q_{q}\neq\emptyset$ . Thus, we proved statement (i). Again, notice that $w_{j}\in N(x_{j})$ for all $j\in[q-1]$ (See Step 11). Thus, statement (ii) follows. Next, we prove statement (iii), which is similar to the proof of it in the base case. Notice that in any iteration of the while loop (after the iteration $h^{\star}$ ), in Step 8, we may add a vertex $v_{r^{\prime}}$ to $B_{i}$ . If this happens, then we know that $N(x_{i})\subseteq P\cup N(v_{r^{\prime}})$ , where $P$ is a subset of $\bigcup_{j\in[q-1]}Q_{j}$ . That is, all the vertices in $N(x_{i})\setminus P$ are adjacent to $v_{r^{\prime}}$ . This implies that $v_{r^{\prime}}$ is adjacent to all the vertices in $N(x_{i})\setminus(\bigcup_{j\in[q-1]}Q_{j})$ . Since $x_{i}\in Q_{i}$ , considered in iteration $h^{\star}$ , $d_{G}(v_{r^{\prime}})\leq d_{G}(x_{i})$ (See Step 5). This completes the proof of the claim. $\hfill\vartriangleleft$

Figure 2: Here the vertex

v\in B_{i}

in the biclique

A_{i}

(right side). The number of neighbors of

v

outside

A_{i}

(blue edges) cannot be more than

|P|

as

d_{G}(v)\leq d_{G}(x_{i})=|N_{G}(x_{i})|

and

v

has

|N(x)\setminus P|

neighbours in the biclique

A_{i}

.

Now suppose $q^{\star}\geq k+1$ . Then, by Statements (i) and (ii) in Claim 11, we get that $(Q_{k},\cdots,Q_{1})$ is a partial Grundy coloring of the graph induced on $\bigcup_{j\in[q^{\star}-1]}Q_{j}$ . Thus, if the algorithm executes Step 18, then it is correct because of Claim 5.

Now suppose $q^{\star}\leq k$ . Then the algorithm executes Step 21 and outputs the sets $A_{1},\dots,A_{q^{\star}-1}$ and $S_{1},\dots,S_{q^{\star}-1}$ . Statement (iii) in Claim 11 implies that each $A_{j}$ is a biclique in $G$ , where $j\in[q^{\star}-1]$ . Also, note that $S_{j}$ is a biclique in $G$ as it is induced on the set $N[x_{j}]$ , for each $j\in[q^{\star}-1]$ . Let $F$ be the union of the edges in the bicliques $A_{1},\dots,A_{q^{\star}-1}$ and $S_{1},\dots,S_{q^{\star}-1}$ . Next, we prove that for any $v\in L$ , $d_{G-F}(v)\leq k^{2}$ . Let $X=\{x_{1},\ldots,x_{q^{\star}-1}\}$ . It is easy to see that $|Q_{j}|\leq k$ and $L\cap Q_{j}=\{x_{j}\}\subseteq X$ , for all $j\in[q^{\star}-1]$ (See Steps 11-13). Hence, $|\bigcup_{j\in[q^{\star}]}Q_{j}|\leq k^{2}$ . Let $v$ be an arbitrary vertex in $L$ . Note that if $v\in X$ , the degree of $v$ in $G-F$ is zero (by the definition of $S_{j}$ ). Next, suppose that $v\in L\setminus X$ . Since $L\subseteq\bigcup_{j\in[q^{\star}-1]}(Q_{j}\cup B_{j})$ (this is the condition for while loop to exit) and $L\cap Q_{j}\subseteq X$ for all $j\in[q^{\star}-1]$ , $v$ belongs to $B_{i}$ for some $i\in[q^{\star}-1]$ . By statement (iii) in Claim 11, $v$ is adjacent to all the vertices in $N(x_{i})\setminus(\bigcup_{j\in[q^{\star}-1]}Q_{j})$ and $d_{G}(v)\leq d_{G}(x_{i})$ . Recall that the biclique $A_{i}$ is the graph with bipartition $B_{i}$ and $N(x_{i})\setminus(\bigcup_{j\in[q^{\star}-1]}Q_{j})$ . Moreover $v\in B_{i}$ and $d_{G}(v)\leq d_{G}(x_{i})=|N_{G}(x_{i})|$ . This implies that the number of neighbors of $v$ that does not belong to $A_{i}$ is at most $|\bigcup_{j\in[q^{\star}-1]}Q_{j}|$ , which is upper bounded by $k^{2}$ . Therefore, the degree of $v$ in $G-F$ is at most $k^{2}$ . See Figure 2 for an illustration. This concludes the proof. $\hfill\blacktriangleleft$

3.2 FPT Algorithm for Partial Grundy Coloring

In this section, we design an FPT algorithm ${\cal A}$ for Partial Grundy Coloring when the input has a structure dictated the second item of Lemma 9. Then, we explain how to get an FPT algorithm for Partial Grundy Coloring on general graphs using ${\cal A}$ and Theorem 2. Moreover, our algorithm ${\cal A}$ will provide a faster algorithm for Partial Grundy Coloring on $d$ -degenerate graphs, improving the result in [1]. Toward the first task, we define the following problem.

Structural Partial Grundy Coloring (SPGC ) Input: Positive integers $k,d,\ell\in{\mathbb{N}}$ , a graph $G$ , and $\ell$ bicliques $A_{1},\dots,A_{\ell}$ in $G$ such that $G-F$ is $d$ -degenerate, where $F$ is the union of the edges in the above bicliques. Question: Decide if there is a partial Grundy coloring for $G$ using at least $k$ colors.

First, we design a randomized polynomial time algorithm ${\cal A}_{1}$ for SPGC with a success probability at least $(k(d+1))^{-2k^{2}-k}\cdot 2^{-\ell k}$ . We increase the probability of success to a constant by running ${\cal A}_{1}$ multiple times. Finally, we explain the derandomization of our algorithm. Then we prove Theorem 1 using this algorithm and our structural result (Theorem 2). To design the algorithm ${\cal A}_{1}$ , we use the following result of Lokshtanov et al. [28].

Proposition 12 (Lemma 1.1. [28]).

There is a linear-time randomized algorithm that, given a $d$ -degenerate graph $H$ and an integer $k$ , outputs an independent set $Y$ such that for any independent set $X$ in $H$ with $|X|\leq k$ , the probability that $X\subseteq Y$ is at least $\left(\binom{k(d+1)}{k}\cdot k(d+1)\right)^{-1}$ .

The algorithm ${\cal A}_{1}$ has the following steps.

1.

Color all vertices in $V(G)$ uniformly and independently at random with colors from the set $[k]$ . Let the obtained coloring be $\phi:V(G)\rightarrow[k]$ , and $Z_{i}=\phi^{-1}(i)$ , for each $i\in[k]$ .
2.

For each $i\in[\ell]$ , let $A_{i}=(L_{i}\uplus R_{i},E_{i})$ . For each $j\in[k]$ and $i\in[\ell]$ , uniformly at randomly assign $P_{j,i}:=L_{i}$ or $P_{i}:=R_{i}$ . That is, with probability $\frac{1}{2}$ , $P_{j,i}:=L_{i}$ and with probability $\frac{1}{2}$ , $P_{j,i}:=R_{i}$ . Let $D_{j}=\bigcup_{i\in[\ell]}P_{j,i}$ .
3.

Now for each $j\in[k]$ , we apply the algorithm in Proposition 12 for $(G[Z_{j}-D_{j}],k)$ to obtain an independent set $Y_{j}$ .
4.

If $(Y_{1},\ldots,Y_{k})$ is a $k$ -partial Grundy witness of $G$ , then output Yes, else, output No.

Since the algorithm in Proposition 12 runs in linear time, the algorithm ${\cal A}_{1}$ can be implemented to run in linear time because $Z_{1},\ldots,Z_{k}$ is a partition of $V(G)$ . Clearly, if the algorithm ${\cal A}_{1}$ outputs Yes, then $G$ has a $k$ -Partial Grundy witness and hence $G$ has a partial Grundy coloring using at least $k$ colors. We can prove that if $G$ has a $k$ -Partial Grundy witness the algorithm ${\cal A}_{1}$ outputs Yes with probability $(k(d+1))^{-2k^{2}-k}\cdot 2^{-\ell k}$ .

Also, by running ${\cal A}_{1}$ , $3\cdot(k(d+1))^{2k^{2}+k}2^{\ell k}$ times and outputting Yes if at least one of the runs outputs a Yes, and outputs No, otherwise, we can boost the success probability to $2/3$ , and thus obtain the following result.

Theorem 13.

There is a randomized algorithm for SPGC running in time ${\mathcal{O}}((k(d+1))^{2k^{2}+k}\cdot 2^{\ell k}\cdot(m+n))$ . In particular, if $(G,k)$ is a no-instance then with probability $1$ the algorithm outputs No; and if $(G,k)$ is a yes-instance then with probability $2/3$ the algorithm outputs Yes.

Theorem 2 and 13 imply the following theorem.

Theorem 14.

There is a randomized algorithm for Partial Grundy Coloring running in time $2^{{\mathcal{O}}(k^{4})}n^{{\mathcal{O}}(1)}$ . In particular, if $(G,k)$ is a no-instance then with probability $1$ the algorithm outputs No; and if $(G,k)$ is a yes-instance then with probability $2/3$ the algorithm outputs Yes.

Proof Sketch.

First we run the algorithm mentioned in Theorem 2. If it concludes that $G$ has a partial Grundy coloring with at least $k$ colors, then we output Yes. Otherwise, we get at most $2k^{3}$ induced bicliques $A_{1}\cdots,A_{\ell}$ in $G$ such that the following holds. For any $v\in V(G)$ , the degree of $v$ in $G-F$ is at most $k^{3}$ , where $F$ is the union of the edges in the above bicliques. That is the degeneracy of $G-F$ is at most $k^{3}$ . Then, we apply Theorem 13, and ouputs accordingly. $\hfill\blacktriangleleft$

The derandomization of our algorithm can be found in the full version.

4 FPT Algorithm for Grundy Coloring on $K_{i,j}$ -free Graphs

This section aims to prove Theorem 3. Consider fixed $i,j\in\mathbb{N}\setminus\{0\}$ , where $i\geq j$ . Recall that a graph is $K_{i,j}$ -free if it does not contain a subgraph isomorphic to $K_{i,j}$ . We call the special case of Grundy Coloring where the input graph is $K_{i,j}$ -free, $K_{i,j}$ -Free Grundy Coloring. Let $(G,k)$ be an instance of $K_{i,j}$ -Free Grundy Coloring. We begin by intuitively explaining the flow of our algorithm.

Consider a Grundy coloring $c:V(G)\rightarrow[k^{\prime}]$ of $G$ , where $k^{\prime}\geq k$ , and for each $z\in[k]$ , $c^{-1}(z)\neq\emptyset$ . Furthermore, for $z\in[k^{\prime}]$ , let $C_{z}=c^{-1}(z)$ . Let us focus on the first $k$ color classes, and for $z\in[k]$ , arbitrarily fix a vertex $v_{z}\in C_{z}$ . (Note that $v_{z}$ has a neighbor in $C_{z^{\prime}}$ , for each $z^{\prime}\in[z-1]$ .) We next intuitively describe construction, for each $z\in[k]$ , a set $W_{z}$ initialized to $\{v_{z}\}$ as follows. Basically, for each $v_{z}$ , add an arbitrarily chosen neighbor of it in color class $C_{z^{\prime}}$ , for every $z^{\prime}<z$ . We do the above process exhaustively; whenever we add a vertex to a set $W_{z}$ , we add an arbitrarily chosen neighbor of it from each color class $C_{z^{\prime}}$ to $W_{z^{\prime}}$ , where $z^{\prime}<z$ . Then, let $W=\cup_{z\in[k]}W_{z}$ ; we will call such a set $W$ a $k$ -Grundy set for $G$ and we will show that such a set of size at most $2^{k-1}$ exists (for yes instances). For $z\in[k]$ , let $W_{\leq z}=\cup_{z^{\prime}\in[z]}W_{z^{\prime}}$ and $W_{>z}=\cup_{z^{\prime}\in[k]\setminus[z]}W_{z^{\prime}}$ . Note that $c|_{W}$ is a $k$ -Grundy coloring of $G[W]$ . Also, we will show that $G$ has a Grundy coloring using at least $k$ colors if and only if some subgraph of $G$ has a Grundy coloring using exactly $k$ colors. We remark that the above result and the existence of $W$ are the same as the results of Gyárfás et al. [22] and Zaker [38], although, for the sake of convenience, we state it here slightly differently. If we can identify all the vertices in $W$ (or some other $k$ -Grundy set), then we will be done. The first step of our algorithm will be to use the technique of color coding to randomly color the vertices of $G$ using $k$ colors so that, for each $z\in[k]$ , $v\in W_{z}$ is colored $z$ ; such a coloring will be a nice coloring and it will be denoted by $\chi$ .

The next step of our algorithm is inspired by the design of FPT algorithms based on computations of “representative sets” [30, 19]. To this end, we will interpret $W$ in a “tree-like” fashion. With this interpretation, in a bottom-up fashion, for each $z\in[k]$ and $v\in X_{z}$ , we will compute a family $\operatorname{\mathcal{F}}^{\prime}_{z,v}$ , so that, if $v\in W_{z}$ , then there will be $W^{\prime}\in\operatorname{\mathcal{F}}^{\prime}_{z,v}$ so that $W^{\prime}\cup W_{>z}$ is also a $k$ -Grundy set for $G$ . We will now formalize the above steps.

Grundy Tree & Grundy Witness.

We recall the Definition 4 from Section 1, and obtain some properties regarding it.

Observation 15 ( $\spadesuit$ ).

For $k\in\mathbb{N}\setminus\{0\}$ , for the $k$ -Grundy tree $(T_{k},\ell_{k})$ , $|V(T_{k})|=2^{k-1}$ .

Observation 16 ( $\spadesuit$ ).

Consider $k\in\mathbb{N}\setminus\{0\}$ and the $k$ -Grundy tree $(T_{k},\ell_{k})$ . We have $|\ell^{-1}(k)|=1$ and for each $z\in[k-1]$ , $|\ell^{-1}_{k}(z)|=2^{k-z-1}$ .

Next, we define the notion of $k$ -Grundy witness in a graph $G$ .

Definition 17.

Consider $k\in\mathbb{N}\setminus\{0\}$ and a graph $G$ . A $k$ -Grundy witness for $G$ is a function $\omega:V(T_{k})\rightarrow V(G)$ , where $(T_{k},\ell_{k})$ is the $k$ -Grundy tree, such that: 1) for each $z\in[k]$ , $\{\omega(t)\mid t\in V(T_{k})\mbox{ and }\ell_{k}(t)=z\}$ is an independent set in $G$ , 2) for each $t,t^{\prime}\in V(T_{k})$ , if $\ell_{k}(t)\neq\ell_{k}(t^{\prime})$ then $\omega(t)\neq\omega(t^{\prime})$ , and 3) for each $(t,t^{\prime})\in A(T_{k})$ , we have $\{\omega(t),\omega(t^{\prime})\}\in E(G)$ .

Figure 3: An illustration of a graph

G

that admits a

4

-Grundy coloring (on the left) and a

4

-Grundy-witness

\omega

(on the right).

Recall that for $k\in\mathbb{N}\setminus\{0\}$ , for the $k$ -Grundy tree $(T_{k},\ell_{k})$ , $T_{k}$ is the tree obtained by adding a root vertex $r_{k}$ attached to the roots of (pairwise vertex disjoint) trees $T_{k-1},T_{k-2},\cdots,T_{1}$ , where for each $z\in[k-1]$ , $(T_{z},\ell_{z})$ is the $z$ -Grundy tree. We have the following observation.

Observation 18 ( $\spadesuit$ ).

Consider $k\in\mathbb{N}\setminus\{0\}$ , a graph $G$ and a $k$ -Grundy witness $\omega:V(T_{k})\rightarrow V(G)$ for $G$ . For each $z\in[k]$ , $\omega|_{V(T_{z})}$ is a $z$ -Grundy witness for $G$ .

The next observation is a partial Grundy counterpart of Observation 5.

Observation 19 ( $\spadesuit$ ).

Consider a graph $G$ , any induced subgraph $\widehat{G}$ of it, and an integer $k\in\mathbb{N}$ . If $\widehat{G}$ has a Grundy coloring that uses exactly $k$ colors, then $G$ has a Grundy coloring that uses at least $k$ colors.

In the following two lemmas, we show that the existence of a $k$ -Grundy witness for a graph is equivalent to the graph admitting a Grundy coloring with at least $k$ colors.

Lemma 20.

For any $k\in\mathbb{N}\setminus\{0\}$ and a graph $G$ , if $G$ has a $k$ -Grundy witness, then $G$ has a Grundy coloring with at least $k$ colors.

Proof.

Consider a graph $G$ and any $k\in\mathbb{N}\setminus\{0\}$ . For a $k$ -Grundy witness $\omega:V(T_{k})\rightarrow V(G)$ of $G$ , let $\widehat{V}_{\omega}=\{\omega(t)\mid t\in V(T_{k})\}$ , and for each $z\in[k]$ , let $\widehat{V}_{\omega,z}=\{\omega(t)\mid t\in V(T_{k})\mbox{ and }\ell_{k}(t)=z\}$ . Note that from item 2 of Definition 17, $\widehat{V}_{\omega,1},\widehat{V}_{\omega,2},\cdots,\widehat{V}_{\omega,k}$ is a partition of $\widehat{V}_{\omega}$ , where none of the parts are empty. Let $c_{\omega}:\widehat{V}_{\omega}\rightarrow[k]$ be the function such that for each $z\in[k]$ and $v\in\widehat{V}_{\omega,z}$ , we have $c_{\omega}(v)=q$ .

For each $k\in\mathbb{N}\setminus\{0\}$ and a $k$ -Grundy witness $\omega:V(T_{k})\rightarrow V(G)$ of $G$ , we will prove by induction (on $k$ ) that $c_{\omega}$ is Grundy coloring of $G[\widehat{V}_{\omega}]$ using $k$ colors. The above statement, together with Observation 19, will give us the desired result.

The base case is $k=1$ , where $T_{1}$ has exactly one vertex, $r_{1}$ . For any $1$ -Grundy witness, $\omega$ of $G$ , note that $c_{\omega}(\omega(r_{1}))=1$ is a Grundy coloring for $G[\{\omega(r_{1})\}]$ using $1$ color. Now for the induction hypothesis suppose that for some $\widehat{k}\in\mathbb{N}\setminus\{0,1\}$ , for each $0<k<\widehat{k}$ , the statement is true. Now we will prove the statement for $k=\widehat{k}$ , and to this end, we consider a $k$ -Grundy witness $\omega:V(T_{k})\rightarrow[k]$ , where $r_{k}$ is the root of $T_{k}$ . Recall that $T_{k}$ is the tree obtained by adding a root vertex $r_{k}$ attached to the roots of (pairwise vertex disjoint) trees $T_{k-1},T_{k-2},\cdots,T_{1}$ , where for each $z\in[k-1]$ , $(T_{z},\ell_{z})$ is the $z$ -Grundy tree, and $T_{z}$ is rooted at $r_{z}$ . Let $V^{\prime}=\widehat{V}_{\omega}\setminus\widehat{V}_{\omega,k}$ , and consider a vertex $v\in\widehat{V}_{\omega,z^{*}}$ , where $z^{*}\in[k-1]$ . We will argue that for each $z^{\prime}\in[z^{*}-1]$ , $N_{G}(v)\cap\widehat{V}_{\omega,z^{\prime}}\neq\emptyset$ . Note that there must exists $z\in[k-1]$ and $t\in V(T_{z})$ such that $\omega(t)=v$ and $\ell_{z}(v)=z^{*}$ , and we arbitrarily choose one such $z$ and $t$ . Let $V_{z}=\{\omega(t)\mid t\in V(T_{z})\}$ . From Observation 18, $\omega_{z}=\omega|_{V(T_{z})}$ is a $z$ -Grundy witness for $G$ . Thus, from our induction hypothesis, $c_{\omega_{z}}=c_{\omega}|_{V_{z}}$ is a Grundy coloring for $G[V_{z}]$ . From the above we can conclude that for each $q^{\prime}\in[z^{*}-1]$ , $N_{G}(v)\cap\widehat{V}_{\omega,z^{\prime}}\neq\emptyset$ . Now consider the vertex $\omega(r_{k})=v^{*}_{k}$ and any $z\in[k-1]$ . Note that $\ell_{k}(r_{z})=z$ and from item 3 of Definition 17, we can obtain that $\{v^{*}_{k},\omega(r_{z})\}\in E(G)$ . From the above discussions, we can obtain that $c_{\omega}$ is Grundy coloring of $G[\widehat{V}_{\omega}]$ using at least $z$ colors. This concludes the proof. $\hfill\blacktriangleleft$

Lemma 21.

For any $k\in\mathbb{N}\setminus\{0\}$ and a graph $G$ , if $G$ has a Grundy coloring with at least $k$ colors, then $G$ has a $k$ -Grundy witness.

Proof.

Consider a Grundy coloring $c:V(G)\rightarrow[k^{\prime}]$ of $G$ with $k^{\prime}\geq k$ colors, and for each $q\in[k^{\prime}]$ , let $C_{q}=c^{-1}(q)$ . We construct a Grundy witness $\omega:V(T_{k})\rightarrow V(G)$ by processing labels of $T_{k}$ starting at $k$ and iteratively proceeding to smaller labels as follows while maintaining the below invariants.
Pre-condition: When we begin processing a label $q\in[k-1]$ , for each $t\in V(T_{k})$ with $\ell_{k}(t)\geq q$ , we have fixed the vertex $\omega(t)$ .
Post-condition: After processing label $q\in[k]$ , we have fixed, for each $t\in V(T_{k})$ with $\ell_{k}(t)\geq q$ , and $t^{\prime}\in N_{T_{k}}[t]$ , the vertex $\omega(t^{\prime})$ ; and these are the only vertices in $T_{k}$ for which the vertex in $G$ assigned by $\omega$ is determined.

Note that the pre-condition is vacuously satisfied for $q=k$ . Recall that $T_{k}$ is the tree obtained by adding a root vertex $r_{k}$ attached to the roots $r_{k-1},r_{k-2},\cdots,r_{1}$ of (pairwise vertex disjoint) trees $T_{k-1},T_{k-2},\cdots,T_{1}$ , respectively, where for each $q\in[k-1]$ , $(T_{q},\ell_{q})$ is a $q$ -Grundy tree. Pick any vertex $v_{k}\in C_{k}$ , and set $\omega(r_{k}):=v_{k}$ and for each $q\in[k-1]$ , set $\omega(r_{q}):=w^{k}_{q}$ , where $w^{k}_{q}$ is an arbitrarily chosen neighbor of $v_{k}$ from $C_{q}$ (which exists as $c$ is a Grundy coloring). After the above step, the post-condition is satisfied for $q=k$ .

Now we (iteratively, in decreasing order) consider $q\in[k-1]\setminus\{1\}$ . From the pre-condition for $q$ , we have fixed, for each $t\in V(T_{k})$ with $\ell_{k}(t)\geq q$ , the vertex $\omega(t)$ . Consider $t\in V(T_{k})$ with $\ell_{k}(t)=q$ and let $v_{t}=\omega(t)$ . Let $\widehat{T}_{q}$ be the subtree of $T_{k}$ rooted at $t$ , and let $\widehat{\ell}_{q}=\ell_{k}|_{V(\widehat{T}_{q})}$ . Notice that $(\widehat{T}_{q},\widehat{\ell}_{q})$ is a $q$ -Grundy tree, where $\widehat{T}_{q}$ is the tree obtained from by adding edge between $t$ and the roots $\widehat{r}_{q-1},\widehat{r}_{q-2},\cdots,\widehat{r}_{1}$ of $\widehat{T}_{q-1},\widehat{T}_{q-2},\cdots,\widehat{T}_{1}$ , respectively, where $(\widehat{T}_{q^{\prime}},\ell_{k}|_{V(\widehat{T}_{q^{\prime}})})$ is a $q^{\prime}$ -Grundy tree, for each $q^{\prime}\in[q-1]$ . For each $q^{\prime}\in[q]$ , let $\widehat{w}^{q}_{q^{\prime}}$ be an arbitrarily chosen vertex from $N_{G}(v)\cap C_{q^{\prime}}$ , and we set $\omega(\widehat{r}_{q^{\prime}})=\widehat{w}^{q}_{q^{\prime}}$ . Notice that after the above step, the post-condition is satisfied for $q$ , and the pre-condition is satisfied for $q-1$ .

After we are done processing each $q\in[k]\setminus\{1\}$ , the post-condition for $q=2$ (and the pre-condition of $q=1$ implies that for each $t\in V(T_{k})$ , we have determined the vertex $\omega(t)$ ). Moreover, the construction of $\omega$ implies that all the three conditions in Definition 17 are satisfied. This concludes the proof. $\hfill\blacktriangleleft$

We next summarize the result we obtain from the above two lemmas.

Lemma 22.

Consider any $k\in\mathbb{N}\setminus\{0\}$ and a graph $G$ . The graph $G$ has a $k$ -Grundy witness if and only if $G$ has a Grundy coloring with at least $k$ colors.

Color Coding of $𝑮$ .

We will next use the above lemma to simplify our job in the following sense. Let $\omega:V(T_{k})\rightarrow V(G)$ be a (fixed) $k$ -Grundy witness of $G$ (if it exists), where $(T_{k},k)$ is a $k$ -Grundy tree. Let $\widehat{V}_{\omega}=\{\omega(t)\mid t\in V(T_{k})\}$ , and for each $q\in[k]$ , let $\widehat{V}_{\omega,q}=\{\omega(t)\mid t\in V(T_{k})\mbox{ and }\ell_{k}(t)=q\}$ . Roughly speaking, our new objective will be to find the vertices in $\widehat{V}_{\omega}$ and say that $G[\widehat{V}_{\omega}]$ admits a Grundy coloring with at least $k$ colors, using which we can conclude that $G$ admits a Grundy coloring with at least $k$ colors. We will use the technique of color coding introduced by Alon et al. [2], to color the vertices in $\widehat{V}_{\omega}$ “nicely” as follows. Color each vertex in $G$ uniformly at random using a color from $[k]$ , and let $\chi:V(G)\rightarrow[k]$ be this coloring. A nice coloring is the one where, for each $q\in[k]$ , the coloring assigns the color $q$ to all the vertices in $\widehat{V}_{\omega,q}$ .

We will work with the assumption that $\chi$ is a nice coloring of $G$ , and for each $q\in[k]$ , let $X_{q}=\chi^{-1}(q)$ . Our objective will be to look for a $k$ -Grundy witness $\widehat{\omega}:V(T_{k})\rightarrow V(G)$ , where $(T_{k},k)$ is a $k$ -Grundy tree, such that for each $q\in[k]$ and $t\in V(T_{k})$ with $\ell_{k}(t)=q$ , we have $\widehat{\omega}(t)\in X_{q}$ . To this end, we will store a “Grundy representative family” for each vertex in a bottom-up fashion, starting from $q=1$ . The definition of such a representative is inspired by the $q$ -representative families [30, 19], although here we need a “vectorial” form of representation. To this end, we introduce the following notations and definitions.

Grundy Representative Sets.

Recall we have the coloring $\chi$ of $G$ with color classes $X_{z}=\chi^{-1}(z)$ , for $z\in[k]$ . A vertex subset $A\subseteq V(G)$ is $\chi$ -independent if for each $z\in[k]$ , $A\cap X_{z}$ is an independent set in $G$ . For $p\in\mathbb{N}$ , a family of vertex subsets $\operatorname{\mathcal{F}}$ is a $p$ -family if each set in $\operatorname{\mathcal{F}}$ has size at most $p$ and each $A\in\operatorname{\mathcal{F}}$ if $\chi$ -independent. We will only be working with vectors all of whose entries are from $\mathbb{N}$ without explicitly stating it. For a vector $\overrightarrow{q}=(q_{1},q_{2},\cdots,q_{k})$ , ${\sf sum}(\overrightarrow{q})$ denotes the number $\sum_{z\in[q]}q_{z}$ . For a vector $\overrightarrow{q}=(q_{1},q_{2},\cdots,q_{k})$ and $B\subseteq V(G)$ , we say that the size of $B$ is $\overrightarrow{q}$ , written as $|B|=\overrightarrow{q}$ , if for each $z\in[k]$ , $|B\cap X_{z}|=q_{z}$ . For vertex subsets $A$ and $B$ , $A$ fits $B$ if $A\cup B$ is $\chi$ -independent. For two vectors $\overrightarrow{q_{1}}=(q^{1}_{1},q^{1}_{2},\cdots,q^{1}_{k})$ and $\overrightarrow{q_{2}}=(q^{2}_{1},q^{2}_{2},\cdots,q^{2}_{k})$ , and $\diamond\in\{\leq,\geq,>,<,=\}$ , we write $\overrightarrow{q_{1}}\diamond\overrightarrow{q_{2}}$ if for each $z\in[k]$ , we have $q^{1}_{z}\diamond q^{2}_{z}$ . We next define the notion of $\overrightarrow{q}$ -Grundy representation.

Definition 23.

Consider $p\in\mathbb{N}$ , a vector $\overrightarrow{q}=(q_{1},q_{2},\cdots,q_{k})$ , and a $p$ -family $\operatorname{\mathcal{F}}$ of vertex subsets of $G$ . For a sub-family $\operatorname{\mathcal{F}}^{\prime}\subseteq\operatorname{\mathcal{F}}$ , we say that $\operatorname{\mathcal{F}}^{\prime}$ $\overrightarrow{q}$ -Grundy represents $\operatorname{\mathcal{F}}$ , written as $\operatorname{\mathcal{F}}^{\prime}\subseteq^{\overrightarrow{q}}_{grep}% \operatorname{\mathcal{F}}$ , if the following holds. For any set $B$ of size $\overrightarrow{q}$ , if there is $A\in\operatorname{\mathcal{F}}$ that fits $B$ , then there is $A^{\prime}\in\operatorname{\mathcal{F}}^{\prime}$ that fits $B$ . In the above, $\operatorname{\mathcal{F}}^{\prime}$ is a $\overrightarrow{q}$ -Grundy representative for $\operatorname{\mathcal{F}}$ .

Next, we obtain some properties regarding $\overrightarrow{q}$ -Grundy representatives.

Observation 24 ( $\spadesuit$ ).

Consider $p\in\mathbb{N}$ , a vector $\overrightarrow{q}=(q_{1},q_{2},\cdots,q_{k})$ , and any two $p$ -families $\operatorname{\mathcal{F}}_{1}$ and $\operatorname{\mathcal{F}}_{2}$ . If $\operatorname{\mathcal{F}}^{\prime}_{1}\subseteq^{\overrightarrow{q}}_{grep}% \operatorname{\mathcal{F}}_{1}$ and $\operatorname{\mathcal{F}}^{\prime}_{2}\subseteq^{\overrightarrow{q}}_{grep}% \operatorname{\mathcal{F}}_{2}$ , then $\operatorname{\mathcal{F}}^{\prime}_{1}\cup\operatorname{\mathcal{F}}^{\prime}% _{2}\subseteq^{\overrightarrow{q}}_{grep}\operatorname{\mathcal{F}}_{1}\cup% \operatorname{\mathcal{F}}_{2}$ .

Consider $p\in\mathbb{N}$ and $v\in V(G)$ . For a family $\operatorname{\mathcal{F}}$ over $V(G)$ , $\operatorname{\mathcal{F}}+v$ denotes the family $\{A\cup\{v\}\mid A\in\operatorname{\mathcal{F}}\mbox{ and $A\cup\{v\}$ is $% \chi$-independent}\}$ . Similarly, $\operatorname{\mathcal{F}}-v$ denotes the family $\{A\setminus\{v\}\mid A\in\operatorname{\mathcal{F}}\}$ . A $p$ -family $\operatorname{\mathcal{F}}$ is a $(p,v)$ -family if for each $A\in\operatorname{\mathcal{F}}$ , we have $v\in A$ .

Observation 25 ( $\spadesuit$ ).

Consider $p\in\mathbb{N}$ , a vector $\overrightarrow{q}=(q_{1},q_{2},\cdots,q_{k})$ , a vertex $v\in V(G)$ and a $(p,v)$ -family $\operatorname{\mathcal{F}}$ . Let $\overrightarrow{h}$ be the vector obtained from $\overrightarrow{q}$ by increasing its $\chi(v)$ th coordinate by $1$ . If $\operatorname{\mathcal{F}}^{\prime}\subseteq^{{\overrightarrow{h}}}_{grep}% \operatorname{\mathcal{F}}-v$ and $\operatorname{\mathcal{F}}^{\prime\prime}\subseteq^{{\overrightarrow{q}}}_{% grep}\operatorname{\mathcal{F}}-v$ , then $(\operatorname{\mathcal{F}}^{\prime}+v)\cup(\operatorname{\mathcal{F}}^{\prime% \prime}+v)\subseteq^{{\overrightarrow{q}}}_{grep}\operatorname{\mathcal{F}}$ .

For a $p_{1}$ -family $\operatorname{\mathcal{F}}_{1}$ and a $p_{2}$ -family $\operatorname{\mathcal{F}}_{2}$ , we define a $(p_{1}+p_{2})$ -family, $\operatorname{\mathcal{F}}_{1}\star\operatorname{\mathcal{F}}_{2}=\{A_{1}\cup A% _{2}\mid A_{1}\in\operatorname{\mathcal{F}}_{1},A_{2}\in\operatorname{\mathcal% {F}}_{2},\mbox{ and $A_{1}\cup A_{2}$ is $\chi$-independent}\}$ . The following lemma will be helpful in obtaining a $\overrightarrow{q}$ -representative for $\operatorname{\mathcal{F}}_{1}\star\operatorname{\mathcal{F}}_{2}$ .

Lemma 26.

Consider a $p_{1}$ -family $\operatorname{\mathcal{F}}_{1}$ , a $p_{2}$ -family $\operatorname{\mathcal{F}}_{2}$ , and a vector $\overrightarrow{q}=(q_{1},q_{2},\cdots,q_{k})$ , where ${\sf sum}(\overrightarrow{q})+p_{1}+p_{2}\leq 2^{k-1}$ . Let $\operatorname{\mathcal{F}}^{\prime}_{1}\subseteq\operatorname{\mathcal{F}}_{1}$ be a $p_{1}$ -family such that for every vector $\overrightarrow{q_{1}}\geq\overrightarrow{q}$ with ${\sf sum}(\overrightarrow{q_{1}})\leq{\sf sum}(\overrightarrow{q})+p_{2}$ , $\operatorname{\mathcal{F}}^{\prime}_{1}\subseteq^{{\overrightarrow{q_{1}}}}_{% grep}\operatorname{\mathcal{F}}_{1}$ . Similarly, consider a $p_{2}$ -family $\operatorname{\mathcal{F}}^{\prime}_{2}\subseteq\operatorname{\mathcal{F}}_{2}$ such that for every vector $\overrightarrow{q_{2}}\geq\overrightarrow{q}$ with ${\sf sum}(\overrightarrow{q_{2}})\leq{\sf sum}(\overrightarrow{q})+p_{1}$ , $\operatorname{\mathcal{F}}^{\prime}_{2}\subseteq^{{\overrightarrow{q_{2}}}}_{% grep}\operatorname{\mathcal{F}}_{2}$ . Then, $\operatorname{\mathcal{F}}^{\prime}_{1}\star\operatorname{\mathcal{F}}^{\prime% }_{2}\subseteq^{{\overrightarrow{q}}}_{grep}\operatorname{\mathcal{F}}_{1}% \star\operatorname{\mathcal{F}}_{2}$ .

Proof.

Consider any $B\subseteq V(G)$ of size $\overrightarrow{q}$ for which there is $A\in\operatorname{\mathcal{F}}_{1}\star\operatorname{\mathcal{F}}_{2}$ , such that $A$ fits $B$ . As $A\in\operatorname{\mathcal{F}}_{1}\star\operatorname{\mathcal{F}}_{2}$ , there must exist sets $A_{1}\in\operatorname{\mathcal{F}}_{1}$ , $A_{2}\in\operatorname{\mathcal{F}}_{2}$ , such that $A_{1}\cup A_{2}=A$ .

Let $\overrightarrow{\delta_{1}}=(\delta^{1}_{z}=|(A_{2}\cap X_{z})\setminus B|)_{z% \in[k]}$ . Note that $|B\cup A_{2}|=\overrightarrow{q}+\overrightarrow{\delta_{1}}$ , $A_{1}$ fits $B\cup A_{2}$ and ${\sf sum}(\overrightarrow{q})+{\sf sum}(\overrightarrow{\delta_{1}})\leq{\sf sum% }(\overrightarrow{q})+p_{2}$ . By the premise of the lemma, there exist $A^{\prime}_{1}\in\operatorname{\mathcal{F}}^{\prime}_{1}$ such that $A^{\prime}_{1}$ fits $B\cup A_{2}$ , as $\operatorname{\mathcal{F}}^{\prime}_{1}\subseteq^{{\overrightarrow{q}+% \overrightarrow{\delta_{1}}}}_{grep}\operatorname{\mathcal{F}}_{1}$ . The above implies that $A_{2}$ fits $B\cup A^{\prime}_{1}$ , where $A^{\prime}_{1}\in\operatorname{\mathcal{F}}^{\prime}_{1}$ . Let $\overrightarrow{\delta_{2}}=(\delta^{2}_{z}=|(A^{\prime}_{1}\cap X_{z})% \setminus B|)_{z\in[k]}$ , and note that $|B\cup A^{\prime}_{1}|=\overrightarrow{q}+\overrightarrow{\delta_{2}}$ , $A_{2}$ fits $B\cup A^{\prime}_{1}$ and ${\sf sum}(\overrightarrow{q})+{\sf sum}(\overrightarrow{\delta_{2}})\leq{\sf sum% }(\overrightarrow{q})+p_{1}$ . Again, as $\operatorname{\mathcal{F}}^{\prime}_{2}\subseteq^{{\overrightarrow{q}+% \overrightarrow{\delta_{2}}}}_{grep}\operatorname{\mathcal{F}}_{2}$ , there exists $A^{\prime}_{2}\in\operatorname{\mathcal{F}}^{\prime}_{2}$ such that $A^{\prime}_{2}$ fits $B\cup A^{\prime}_{1}$ . The above discussions imply that, $A^{\prime}_{1}\in\operatorname{\mathcal{F}}^{\prime}_{1}$ , $A^{\prime}_{2}\in\operatorname{\mathcal{F}}^{\prime}_{2}$ , and thus $A^{\prime}_{1}\cup A^{\prime}_{2}\in\operatorname{\mathcal{F}}^{\prime}_{1}% \star\operatorname{\mathcal{F}}^{\prime}_{2}$ , where $A^{\prime}_{1}\cup A^{\prime}_{2}$ fits $B$ . This concludes the proof. $\hfill\blacktriangleleft$

Recall that $G$ is a $K_{i,j}$ -free graph, where $i\geq j$ . Consider any computable function $f(k)$ . Let $\eta_{f(k)}:=i\cdot f(k)\cdot k$ ; where we skip the subscript $f(k)$ when the context is clear. Also, for $p\in\mathbb{N}$ , let $\alpha_{p}:=3\cdot k\cdot(p\eta)^{i+1}$ ; again we skip the subscript $p$ , when the context is clear. We next state the main lemma, which lies at the crux of our algorithm.

Lemma 27 ( $\spadesuit$ ).

Consider any computable function $f:\mathbb{N}\rightarrow\mathbb{N}\setminus\{0\}$ . There is an algorithm that takes as input $k\in\mathbb{N}\setminus\{0\}$ , $p\in\mathbb{N}$ , a vector $\overrightarrow{q}=(q_{1},q_{2},\cdots,q_{k})$ , and a $p$ -family $\operatorname{\mathcal{F}}$ of vertex subsets of a $K_{i,j}$ -free graph $G$ on $n$ vertices with a coloring $\chi:V(G)\rightarrow[k]$ , where $p+{\sf sum}(\overrightarrow{q})\leq f(k)$ . In time bounded by $\operatorname{\mathcal{O}}(\alpha^{2p+{\sf sum}(\overrightarrow{q})}\cdot p% \cdot|\operatorname{\mathcal{F}}|)$ we can find $\operatorname{\mathcal{F}}^{\prime}\subseteq\operatorname{\mathcal{F}}$ with at most $\alpha^{2p+{\sf sum}(\overrightarrow{q})}$ sets such that $\operatorname{\mathcal{F}}^{\prime}\subseteq^{\overrightarrow{q}}_{\sf grep}% \operatorname{\mathcal{F}}$ .

In the remainder of this section, we prove Theorem 3, assuming the correctness of Lemma 27.

Some Useful Notations.

For $z\in\mathbb{N}\setminus\{0\}$ and $z^{\prime}\in[z]$ , let $\gamma_{z,z^{\prime}}$ be the number of vertices with label $z^{\prime}$ in the $z$ -Grundy tree $(T_{z},\ell_{z})$ , i.e., $\gamma_{z,z^{\prime}}=|\ell_{z}^{-1}(z^{\prime})|$ .

Let $\overrightarrow{q}^{*}=\overrightarrow{\gamma_{k}}:=(\gamma_{k,1},\gamma_{k,2}% ,\cdots,\gamma_{k,k})$ . We will define a vector $\overrightarrow{q_{z}}^{*}=(q^{*}_{z,1},q^{*}_{z,2},\cdots,q^{*}_{z,k})$ , for every $z\in[k]$ . Intuitively speaking, the $z^{\prime}$ th entry of $\overrightarrow{q_{z}}^{*}$ will denote the number of vertices with label $z^{\prime}$ appearing in $T_{k}$ after removing exactly one subtree rooted at a vertex with label $z$ . Formally, for each $z^{\prime}\in\{z+1,z+2,\cdots,k\}$ , we have $q^{*}_{z,z^{\prime}}=\gamma_{k,z^{\prime}}$ , and for each $z^{\prime}\in[z]$ , $q^{*}_{z,z^{\prime}}=\gamma_{k,z^{\prime}}-\gamma_{z,z^{\prime}}$ . For $z\in[k]$ , we let $\overrightarrow{0_{z}}$ be the vector of dimension $k$ where the $z$ th entry is $1$ , and all the other entries are $0$ .

For a tree $\widehat{T}$ rooted at $r$ and $t\in V(\widehat{T})$ , we let $\widehat{T}^{t}$ be the subtree of $\widehat{T}$ rooted at $t$ , i.e., $V(\widehat{T}^{t})=\{t^{\prime}\in V(\widehat{T})\mid t^{\prime}=t,\mbox{ or $% t^{\prime}$ is a descendant of $t$ in }\widehat{T}\}$ and $\widehat{T}^{t}=\widehat{T}[V(\widehat{T}^{t})]$ .

For a set $W\subseteq V(G)$ , we say that $W$ is a $k$ -Grundy set if there is a $k$ -Grundy witness $\omega:V(T_{k})\rightarrow W$ for $G$ . Moreover, $W$ is minimal if no proper subset $W^{\prime}\subset W$ is a $k$ -Grundy set for $G$ . For a $k$ -Grundy set $W$ and a $k$ -Grundy witness $\omega:V(T_{k})\rightarrow W$ for $G$ , for $t\in V(T_{k})$ , we let $W_{{\sf sub},t}=\{\omega(t^{\prime})\mid t^{\prime}\in V(T^{t}_{k})\}$ and $W_{{\sf exc},t}=\{\omega(t^{\prime})\mid t^{\prime}\in V(T_{k})\setminus V(T^{% t}_{k})\}$ .

Recall that we have a graph $G$ and a coloring $\chi:V(G)\rightarrow[k]$ , where for $z\in[k]$ , we have $X_{z}=\chi^{-1}(z)$ . For $z\in[k]$ and $v\in V(G)$ , we define $\operatorname{\mathcal{F}}_{z,v}:=\{W\subseteq\cup_{z^{\prime}\in[z]}X_{z^{% \prime}}\mid v\in W,W\mbox{ is $\chi$-independent and }z\leq|W|\leq 2^{z-1}\}$ .

Description of the Algorithm.

The objective of our algorithm will be to compute, for each $z\in[k]$ and $v\in X_{z}$ , a family $\operatorname{\mathcal{F}}^{\prime}_{z,v}\subseteq\operatorname{\mathcal{F}}_{% z,v}$ ; starting from $z=1$ (and then iteratively, for other values of $z$ in increasing order), satisfying the following constraints:

Size Constraint.

$|\operatorname{\mathcal{F}}^{\prime}_{z,v}|\leq\alpha^{2^{k}+1}$ .

Correctness Constraint.

For any $z\in[k]$ and $v\in X_{z}$ , the following holds:

1.

Each $A\in\operatorname{\mathcal{F}}^{\prime}_{z,v}$ is a $z$ -Grundy set in $G$ .
2.

Consider any minimal $k$ -Grundy set $W$ , such that $v\in W$ (if it exists). Furthermore, let $\omega:V({T_{k}})\rightarrow W$ be a $k$ -Grundy witness for $G$ . For any $t\in V(T_{k})$ with $\omega(t)=v$ , where $\overrightarrow{q_{t}}=|W_{{\sf exc},t}|$ , there is $W^{\prime}\in\operatorname{\mathcal{F}}^{\prime}_{z,v}\subseteq\operatorname{% \mathcal{F}}_{z,v}$ such that $W_{{\sf exc},t}\cup W^{\prime}$ is a $k$ -Grundy set in $G$ , i.e., $\operatorname{\mathcal{F}}^{\prime}_{z,v}\subseteq^{{\overrightarrow{q_{t}}}}_% {grep}\operatorname{\mathcal{F}}_{z,v}$ .

Base Case.

We are in our base case when $z=1$ ; note that $[2^{0}]=\{1\}$ . For each $v\in X_{1}$ , set $\operatorname{\mathcal{F}}^{\prime}_{1,v}:=\operatorname{\mathcal{F}}_{1,v}=\{% \{v\}\}$ . Note that $\operatorname{\mathcal{F}}^{\prime}_{1,v}$ satisfies both the size and the correctness constraints.

Recursive Formula.

Consider $z\in[k]\setminus\{1\}$ and $v\in X_{z}$ . We suppose that for each $z^{\prime}\in[z-1]$ and $v^{\prime}\in X_{z^{\prime}}$ , we have computed $\operatorname{\mathcal{F}}^{\prime}_{z^{\prime},v^{\prime}}$ that satisfies both the size and the correctness constraints.

For each $z^{\prime}\in[z-1]$ , we create a family $\operatorname{\mathcal{F}}_{z,v,z^{\prime}}$ , initialized to $\emptyset$ as follows. For each $u\in X_{z^{\prime}}\cap N_{G}(v)$ and $W\in\operatorname{\mathcal{F}}^{\prime}_{z^{\prime},u}$ , if $W\cup\{v\}$ is $\chi$ -independent and $|W\cup\{v\}|\leq 2^{z-1}$ , then add $W\cup\{v\}$ to $\operatorname{\mathcal{F}}_{z,v,z^{\prime}}$ . Note that $|\operatorname{\mathcal{F}}_{z,v,z^{\prime}}|\leq n\cdot\alpha^{2^{k}+1}_{p}$ , where $p=2^{z^{\prime}-1}$ . Using Lemma 27, for each vector $\overrightarrow{q}\leq\overrightarrow{q_{z}}^{*}$ , we compute $\operatorname{\mathcal{F}}^{\prime}_{z,v,z^{\prime},\overrightarrow{q}}% \subseteq^{{\overrightarrow{q}}}_{grep}\operatorname{\mathcal{F}}_{z,v,z^{% \prime}}$ , where $|\operatorname{\mathcal{F}}^{\prime}_{z,v,z^{\prime},\overrightarrow{q}}|\leq% \alpha^{2^{k}}$ , and set $\operatorname{\mathcal{F}}^{\prime}_{z,v,z^{\prime}}=\cup_{\overrightarrow{q}% \leq\overrightarrow{q_{z}}}\operatorname{\mathcal{F}}^{\prime}_{z,v,z^{\prime}% ,\overrightarrow{q}}$ . Note that $\operatorname{\mathcal{F}}^{\prime}_{z,v,z^{\prime}}\leq 2^{(k-1)k}\cdot\alpha% ^{2^{k}}\leq\alpha^{2^{k}+1}$ and we can compute it in time bounded by $\operatorname{\mathcal{O}}(\alpha^{2^{k}+1}\cdot 2^{k-1}\cdot|\operatorname{% \mathcal{F}}_{z,v,z^{\prime}}|)$ .

Next we will iteratively “combine and reduce” the families $\operatorname{\mathcal{F}}^{\prime}_{z,v,z^{\prime}}$ , for $z^{\prime}\in[z]$ , to obtain a family $\widehat{\operatorname{\mathcal{F}}}_{z,v}\subseteq\operatorname{\mathcal{F}}_% {z,v}$ as follows. We set $\widehat{\operatorname{\mathcal{F}}}_{z,v,1}:=\operatorname{\mathcal{F}}^{% \prime}_{z,v,1}$ . Iteratively, (in increasing order), for each $z^{\prime}\in[z-1]\setminus\{1\}$ , we do the following:

1.

Set $\widetilde{\operatorname{\mathcal{F}}}_{z,v,z^{\prime}}:=\widehat{% \operatorname{\mathcal{F}}}_{z,v,z^{\prime}-1}\star\operatorname{\mathcal{F}}^% {\prime}_{z,v,z^{\prime}}$ .
2.

Compute $\widehat{\operatorname{\mathcal{F}}}_{z,v,z^{\prime},\overrightarrow{q}}% \subseteq^{{\overrightarrow{q}}}_{grep}\widetilde{\operatorname{\mathcal{F}}}_% {z,v,z^{\prime}}$ , for each $\overrightarrow{q}\leq\overrightarrow{q_{z^{\prime}}}=\overrightarrow{\gamma_{% k}}-\big{(}\sum_{\widehat{z}\in[z^{\prime}]}(\overrightarrow{\gamma_{k}}-% \overrightarrow{q_{\widehat{z}}}^{*})\big{)}-\overrightarrow{0_{z}}$ , and set $\widehat{\operatorname{\mathcal{F}}}_{z,v,z^{\prime}}=\cup_{\overrightarrow{q}% \leq\overrightarrow{q_{z^{\prime}}}}\widehat{\operatorname{\mathcal{F}}}_{z,v,% z^{\prime},\overrightarrow{q}}$ . Note that $|\widehat{\operatorname{\mathcal{F}}}_{z,v,z^{\prime}}|\leq\alpha^{2^{k}+1}$ and it can be computed in time bounded by $\operatorname{\mathcal{O}}(\alpha^{2^{k}+1}\cdot 2^{k-1}\cdot|\widetilde{% \operatorname{\mathcal{F}}}_{z,v,z^{\prime}}|)$ .

We add each $A\in\widehat{\operatorname{\mathcal{F}}}_{z,v,z-1}$ to $\operatorname{\mathcal{F}}^{\prime}_{z,v}$ , which is a $z$ -Grundy set in $G$ (note that since the size of each set is bounded by $2^{k-1}$ , we can easily do it in the allowed amount of time). In the following lemma, we show that $\operatorname{\mathcal{F}}^{\prime}_{z,v}$ satisfies the correctness constraints.

Lemma 28.

$\operatorname{\mathcal{F}}^{\prime}_{z,v}$ satisfies the correctness constraint.

Proof.

Consider any $v\in X_{z}$ and a minimal $k$ -Grundy set $W$ , such that $v\in W$ (if it exists) and let $\omega:V({T_{k}})\rightarrow W$ be a $k$ -Grundy witness for $G$ . Next consider any $t\in V(T_{k})$ with $\omega(t)=v$ . We will argue that, there is $W^{\prime}\in\operatorname{\mathcal{F}}^{\prime}_{z,v}$ such that $W_{{\sf exc},t}\cup W^{\prime}$ is a $k$ -Grundy set in $G$ . For each $z^{\prime}\in[z-1]$ , let $t_{z^{\prime}}$ be the child of $t$ in $T_{k}$ with $\ell_{k}(t_{z^{\prime}})=z^{\prime}$ and $v_{z^{\prime}}=\omega(t_{z^{\prime}})$ . Note that for each $z^{\prime}\in[z-1]$ , $v_{z^{\prime}}\in X_{z^{\prime}}$ . For each $z^{\prime}\in[z-1]$ , let $\widehat{A}_{z^{\prime}}=\{\omega(t^{\prime})\mid t^{\prime}\in V(T^{t_{z^{% \prime}}}_{k})\}$ , and note that $|\widehat{A}_{z^{\prime}}|\leq 2^{z^{\prime}-1}$ . Now we iteratively take the union of the above sets as follows. For each $z^{\prime}\in[z-1]$ , let $A_{z^{\prime}}=\cup_{\widehat{z}\in[z^{\prime}]}\widehat{A}_{\widehat{z}}$ . Now for each $z^{\prime}\in[z-1]$ , we construct a subset, $B_{z^{\prime}}$ of $W$ that contains $\omega(t^{\prime})$ , for each $t^{\prime}\in V(T_{k})$ that does not belong to the subtrees rooted at any of the vertices $t_{1},t_{2},\cdots,t_{z^{\prime}}$ . Formally, for $z^{\prime}\in[z-1]$ , let $B_{z^{\prime}}=\{\omega(t^{\prime})\mid t^{\prime}\in V(T_{k})\setminus\big{(}% \bigcup_{z^{\prime\prime}\in[z^{\prime}]}V(T^{t_{z^{\prime\prime}}}_{k})\big{)}\}$ . Furthermore, let $\overrightarrow{s_{z^{\prime}}}$ be the size of $B_{z^{\prime}}$ . Notice that for each $z^{\prime}\in[z-1]$ , all of the following holds:

1.

$\overrightarrow{s_{z^{\prime}}}\leq\overrightarrow{q_{z^{\prime}}}$ ,
2.

$|A_{z^{\prime}}|\leq\sum_{\widehat{z}\in[z^{\prime}]}2^{\widehat{z}-1}$ ,
3.

$|\widehat{A}_{z^{\prime}}|\leq 2^{z^{\prime}-1}$ and $\widehat{A}_{z^{\prime}}\in\operatorname{\mathcal{F}}_{z^{\prime},v_{z^{\prime% }}}$ ,
4.

$A_{z^{\prime}}\cup B_{z^{\prime}}=W$ , and thus, $A_{z^{\prime}}$ fits $B_{z^{\prime}}$ .

We will now iteratively define sets $A^{\prime}_{1},A^{\prime}_{2},\cdots,A^{\prime}_{z-1}$ and functions $\omega_{1},\omega_{2}\cdots,\omega_{z-1}$ , and we will ensure that, for each $z^{\prime}\in[z-1]$ , we have: i) $\omega_{z^{\prime}}:V(T_{k})\rightarrow A^{\prime}_{z^{\prime}}\cup B_{z^{% \prime}}$ is a $k$ -Grundy witness for $G$ , ii) for each $z^{\prime}\in[z-1]$ and $t^{\prime}\in V(T_{k})\setminus\big{(}\bigcup_{z^{\prime\prime}\in[z^{\prime}]% }V(T^{t_{z^{\prime\prime}}}_{k})\big{)}$ , we have $\omega_{z^{\prime}}(t^{\prime})=\omega(t^{\prime})$ , iii) $A^{\prime}_{z^{\prime}}\in\widehat{\operatorname{\mathcal{F}}}_{z,v,z^{\prime}}$ , and iv) for each $z^{\prime\prime}\in[z^{\prime}]$ , there is a minimal $z^{\prime\prime}$ -Grundy set $A^{\prime}_{z^{\prime},z^{\prime\prime}}\subseteq A^{\prime}_{z^{\prime}}$ , where the unique vertex in $A^{\prime}_{z^{\prime},z^{\prime\prime}}\cap X_{z^{\prime\prime}}$ is a neighbor of $v$ .

Recall that $z\geq 2$ and $\widehat{\operatorname{\mathcal{F}}}_{z,v,1}=\operatorname{\mathcal{F}}^{% \prime}_{z,v,1}\subseteq\operatorname{\mathcal{F}}_{z,v,1}$ . Also, we have $\widehat{A}_{1}=A_{1}=\{u^{\prime}\}$ , for some $u^{\prime}\in N_{G}(v)\cap X_{1}$ , and $A_{1}\cup B_{1}=W$ is a $k$ -Grundy set. Thus, there must exist $A^{\prime}_{1}\in\operatorname{\mathcal{F}}^{\prime}_{z,v,1}$ such that $A^{\prime}_{1}\cup B_{1}$ is $\chi$ -independent. Moreover by the construction of $\operatorname{\mathcal{F}}^{\prime}_{z,v,1}$ , $A^{\prime}_{1}=\{u\}$ , for some $u\in N_{G}(v)\cap X_{1}$ . Let $\omega_{1}:V(T_{k})\rightarrow A^{\prime}_{1}\cup B_{1}$ be the function such that for each $t^{\prime}\in V(T_{k})\setminus\{t_{1}\}$ , we have $\omega_{1}(t^{\prime})=\omega(t^{\prime})$ and $\omega_{1}(t_{1})=u$ . As $A^{\prime}_{1}\cup B_{1}$ is $\chi$ -independent and $\{u,v\}\in E(G)$ , we can obtain that $\omega_{1}$ is a $k$ -Grundy witness for $G$ . Note that if $z=2$ , then by the above arguments, we have constructed the desired sets and functions, which is just the set $A^{\prime}_{1}$ and the function $\omega_{1}$ .

We now consider the case when $z^{\prime}\geq 2$ . Also, we assume that for some $\widehat{z}\in[z-2]$ , for each $z^{\prime}\in[\widehat{z}]$ , we have constructed $A^{\prime}_{z^{\prime}}$ and $\omega_{z^{\prime}}$ satisfying the desired condition. Now we prove the statement for $z^{\prime}=\widehat{z}+1$ . Note that $A^{\prime}_{z^{\prime}-1}\cup B_{z^{\prime}-1}$ is a $k$ -Grundy set and $\omega_{z^{\prime}-1}:V(T_{k})\rightarrow A^{\prime}_{z^{\prime}-1}\cup B_{z^{% \prime}-1}$ is a $k$ -Grundy witness for $G$ , where $A^{\prime}_{z^{\prime}-1}\in\widehat{\operatorname{\mathcal{F}}}_{z,v,z^{% \prime}}$ . Note that $\widehat{A}_{z^{\prime}}\subseteq B_{z^{\prime}-1}$ . Let $B^{\prime}_{z^{\prime}}=\{\omega_{z^{\prime}-1}(t^{\prime})\mid t^{\prime}\in V% (T_{k})\setminus V(T_{k}^{t_{z^{\prime}}})\}$ . Note that $|B^{\prime}_{z^{\prime}}|\leq\overrightarrow{q_{z^{\prime}}}$ and $\widehat{A}_{z^{\prime}}$ fits $B^{\prime}_{z^{\prime}}$ , and recall that $\widehat{A}_{z^{\prime}}\in\operatorname{\mathcal{F}}_{z^{\prime},v_{z^{\prime% }}}$ . As $\operatorname{\mathcal{F}}^{\prime}_{z^{\prime},v_{z^{\prime}}}\subseteq^{{% \overrightarrow{q}}}_{grep}\operatorname{\mathcal{F}}_{z^{\prime},v_{z^{\prime% }}}$ , for every $\overrightarrow{q}\leq\overrightarrow{q_{z^{\prime}}}$ , there must exists $\widetilde{A}_{z^{\prime}}\in\operatorname{\mathcal{F}}^{\prime}_{z^{\prime},v% _{z^{\prime}}}$ , such that $\widetilde{A}_{z^{\prime}}$ fits $B^{\prime}_{z^{\prime}}$ . By the construction of $\operatorname{\mathcal{F}}^{\prime}_{z^{\prime},v_{z^{\prime}}}$ , we have $v_{z^{\prime}}\in\widetilde{A}_{z^{\prime}}$ and $\widetilde{A}_{z^{\prime}}\cup B^{\prime}_{z^{\prime}}$ is $\chi$ -independent, and also $v\in B^{\prime}_{z^{\prime}}$ . From the above discussions we can conclude that $\widetilde{A}_{z^{\prime}}\cup\{v\}\in\operatorname{\mathcal{F}}_{z,v,z^{% \prime}}$ . Moreover, as $A^{\prime}_{z^{\prime}-1}\in\widehat{\operatorname{\mathcal{F}}}_{z,v,z^{% \prime}-1}$ , $A^{\prime}_{z^{\prime}-1}\subseteq B^{\prime}_{z^{\prime}}$ and $\widetilde{A}_{z^{\prime}}\cup B^{\prime}_{z^{\prime}}$ is $\chi$ -independent, we can obtain that $A^{\prime}_{z^{\prime}-1}\cup\widetilde{A}_{z^{\prime}}\cup\{v\}\in\widehat{% \operatorname{\mathcal{F}}}_{z,v,z^{\prime}-1}\star\operatorname{\mathcal{F}}^% {\prime}_{z,v,z^{\prime}}=\widetilde{\operatorname{\mathcal{F}}}_{z,v,z^{% \prime}}$ . As $\widehat{\operatorname{\mathcal{F}}}_{z,v,z^{\prime}}\subseteq^{{% \overrightarrow{q}}}_{grep}\widetilde{\operatorname{\mathcal{F}}}_{z,v,z^{% \prime}}$ , for every $\overrightarrow{q}\leq\overrightarrow{q_{z^{\prime}}}^{*}$ and $|B_{z^{\prime}}|\leq\overrightarrow{q_{z^{\prime}}}^{*}$ , there must exists $A^{\prime}_{z^{\prime}}\in\widehat{\operatorname{\mathcal{F}}}_{z,v,z^{\prime}}$ such that $A^{\prime}_{z^{\prime}}\cup B_{z^{\prime}}$ is $\chi$ -independent.

As $A^{\prime}_{z^{\prime}}\in\widehat{\operatorname{\mathcal{F}}}_{z,v,z^{\prime}}$ , there must exist $\widehat{C}\in\widehat{\operatorname{\mathcal{F}}}_{z,v,z^{\prime}-1}$ and $C^{\prime}\cup\{v\}\in\operatorname{\mathcal{F}}^{\prime}_{z,v,z^{\prime}}$ , such that $A^{\prime}_{z^{\prime}}=\widehat{C}\cup C^{\prime}\cup\{v\}$ . By the correctness for $z^{\prime}-1$ , $C^{\prime}$ contains for each $z^{\prime\prime}\in[z^{\prime}-1]$ , a minimal $z^{\prime\prime}$ -Grundy set $A^{\prime}_{z^{\prime}-1,z^{\prime\prime}}\subseteq A^{\prime}_{z^{\prime}-1}$ , where the unique vertex in $A^{\prime}_{z^{\prime}-1,z^{\prime\prime}}\cap X_{z^{\prime\prime}}$ is a neighbor of $v$ . Also by the construction of $\operatorname{\mathcal{F}}^{\prime}_{z,v,z^{\prime}}$ , $C^{\prime}$ contains a minimal $z^{\prime}$ -Grundy set $C^{\prime\prime}$ in $G$ , where the unique vertex in $C^{\prime\prime}\cap X_{z^{\prime}}$ is a neighbor of $v$ . From the above discussions, we can conclude that $A^{\prime}_{z^{\prime}}\cup B_{z^{\prime}}$ is a $k$ -Grundy set in $G$ . $\hfill\blacktriangleleft$

Using the above algorithm, we can compute for each $z\in[k]$ and $v\in X_{z}$ , a family $\operatorname{\mathcal{F}}^{\prime}_{z,v}\subseteq\operatorname{\mathcal{F}}_{% z,v}$ that satisfies the correctness and the size constraints, in time bounded by $\alpha^{\operatorname{\mathcal{O}}(2^{k}+1)}\cdot n^{\operatorname{\mathcal{O}% }(1)}$ . Note that $G$ has a Grundy coloring using at least $k$ colors if and only if for some $v\in X_{k}$ , $\operatorname{\mathcal{F}}^{\prime}_{z,v}\neq\emptyset$ . This implies a proof of Theorem 3.

References

[1] Pierre Aboulker, Édouard Bonnet, Eun Jung Kim, and Florian Sikora. Grundy coloring and friends, half-graphs, bicliques. Algorithmica, pages 1–28, 2022. doi:10.1007/S00453-022-01001-2.
[2] Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844–856, 1995. doi:10.1145/210332.210337.
[3] Júlio César Silva Araújo and Cláudia Linhares Sales. Grundy number on p ${}_{\mbox{4}}$ -classes. Electron. Notes Discret. Math., 35:21–27, 2009. doi:10.1016/J.ENDM.2009.11.005.
[4] R. Balakrishnan and T Kavaskar. Interpolation theorem for partial grundy coloring. Discrete Mathematics, 313(8):949–950, 2013. doi:10.1016/J.DISC.2013.01.018.
[5] Rangaswami Balakrishnan and T. Kavaskar. Color chain of a graph. Graphs Comb., 27(4):487–493, 2011. doi:10.1007/S00373-010-0989-7.
[6] Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Yota Otachi. Grundy distinguishes treewidth from pathwidth. In 28th Annual European Symposium on Algorithms (ESA 2020). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020.
[7] Édouard Bonnet, Florent Foucaud, Eun Jung Kim, and Florian Sikora. Complexity of grundy coloring and its variants. Discret. Appl. Math., 243:99–114, 2018. doi:10.1016/J.DAM.2017.12.022.
[8] Gregory J. Chaitin, Marc A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins, and Peter W. Markstein. Register allocation via coloring. Comput. Lang., 6(1):47–57, 1981. doi:10.1016/0096-0551(81)90048-5.
[9] CWK Chen and David YY Yun. Unifying graph-matching problem with a practical solution. In Proceedings of International Conference on Systems, Signals, Control, Computers, volume 55, 1998.
[10] C. A. Christen and S. M. Selkow. Some perfect coloring properties of graphs. Journal of Combinatorial Theory, Series B, 27(1):49–59, 1979. doi:10.1016/0095-8956(79)90067-4.
[11] Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 5. Springer, 2015. doi:10.1007/978-3-319-21275-3.
[12] Lyes Dekar, Brice Effantin, and Hamamache Kheddouci. An incremental distributed algorithm for a partial grundy coloring of graphs. In Ivan Stojmenovic, Ruppa K. Thulasiram, Laurence Tianruo Yang, Weijia Jia, Minyi Guo, and Rodrigo Fernandes de Mello, editors, Parallel and Distributed Processing and Applications, 5th International Symposium, ISPA 2007, Niagara Falls, Canada, August 29-31, 2007, Proceedings, volume 4742 of Lecture Notes in Computer Science, pages 170–181. Springer, 2007. doi:10.1007/978-3-540-74742-0_18.
[13] Reinhard Diestel. Graph theory, volume 173. Springer-Verlag Heidelberg, 2017.
[14] Irit Dinur, Elchanan Mossel, and Oded Regev. Conditional hardness for approximate coloring. SIAM J. Comput., 39(3):843–873, 2009. doi:10.1137/07068062X.
[15] B. Effantin, N. Gastineau, and O. Togni. A characterization of b-chromatic and partial grundy numbers by induced subgraphs. Discrete Mathematics, 339(8):2157–2167, 2016. doi:10.1016/J.DISC.2016.03.011.
[16] P. Erdös, S. T. Hedetniemi, R. C. Laskar, and G. C. E. Prins. On the equality of the partial grundy and upper ochromatic numbers of graphs. Discrete Mathematics, 272(1):53–64, 2003. doi:10.1016/S0012-365X(03)00184-5.
[17] P Fahad. Dynamic Programming using Representative Families. PhD thesis, Homi Bhabha National Institute, 2015.
[18] Uriel Feige and Joe Kilian. Zero knowledge and the chromatic number. J. Comput. Syst. Sci., 57(2):187–199, 1998. doi:10.1006/JCSS.1998.1587.
[19] Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM, 63(4):29:1–29:60, 2016. doi:10.1145/2886094.
[20] N. Goyal and S. Vishwanathan. Np-completeness of undirected grundy numbering and related problems. Unpublished manuscript, 1997.
[21] P. M. Grundy. Mathematics and games. Eureka, 2:6–9, 1939.
[22] András Gyárfás, Zoltán Király, and Jenö Lehel. On-line 3-chromatic graphs i. triangle-free graphs. SIAM J. Discret. Math., 12(3):385–411, 1999. doi:10.1137/S089548019631030X.
[23] F. Havet and L. Sampaio. On the grundy and b-chromatic numbers of a graph. Algorithmica, 65(4):885–899, 2013. doi:10.1007/S00453-011-9604-4.
[24] 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.
[25] Allen Ibiapina and Ana Silva. b-continuity and partial grundy coloring of graphs with large girth. Discrete Mathematics, 343(8):111920, 2020. doi:10.1016/J.DISC.2020.111920.
[26] Hal A. Kierstead and Karin Rebecca Saoub. First-fit coloring of bounded tolerance graphs. Discret. Appl. Math., 159(7):605–611, 2011. doi:10.1016/J.DAM.2010.05.002.
[27] Guy Kortsarz. A lower bound for approximating the grundy number. Discrete Mathematics & Theoretical Computer Science, 9, 2007.
[28] Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma, and Meirav Zehavi. Covering small independent sets and separators with applications to parameterized algorithms. ACM Transactions on Algorithms (TALG), 16(3):1–31, 2020. doi:10.1145/3379698.
[29] Dániel Marx. Graph colouring problems and their applications in scheduling. Periodica Polytechnica Electrical Engineering (Archives), 48(1-2):11–16, 2004.
[30] Dániel Marx. A parameterized view on matroid optimization problems. Theor. Comput. Sci., 410(44):4471–4479, 2009. doi:10.1016/J.TCS.2009.07.027.
[31] Moni Naor, Leonard J Schulman, and Aravind Srinivasan. Splitters and near-optimal derandomization. In Proceedings of IEEE 36th Annual Foundations of Computer Science, pages 182–191. IEEE, 1995. doi:10.1109/SFCS.1995.492475.
[32] B. S. Panda and Shaily Verma. On partial grundy coloring of bipartite graphs and chordal graphs. Discret. Appl. Math., 271:171–183, 2019. doi:10.1016/J.DAM.2019.08.005.
[33] L. Sampaio. Algorithmic aspects of graph colourings heuristics. PhD thesis, University Nice Sophia Antipolis, 2012.
[34] Z. Shi, W. Goddard, S. T. Hedetniemi, K. Kennedy, R. Laskar, and A. McRae. An algorithm for partial grundy number on trees. Discrete Mathematics, 304(1-3):108–116, 2005. doi:10.1016/J.DISC.2005.09.008.
[35] Zixing Tang, Baoyindureng Wu, Lin Hu, and Manouchehr Zaker. More bounds for the grundy number of graphs. J. Comb. Optim., 33(2):580–589, 2017. doi:10.1007/S10878-015-9981-8.
[36] Shaily Verma and B. S. Panda. Grundy coloring in some subclasses of bipartite graphs and their complements. Information Processing Letters, 163:105999, 2020. doi:10.1016/J.IPL.2020.105999.
[37] M. Zaker. Grundy chromatic number of the complement of bipartite graphs. Australasian Journal of Combinatorics, 31:325–330, 2005. URL: http://ajc.maths.uq.edu.au/pdf/31/ajc_v31_p325.pdf.
[38] M. Zaker. Results on the grundy chromatic number of graphs. Discrete mathematics, 306(23):3166–3173, 2006. doi:10.1016/J.DISC.2005.06.044.
[39] Manouchehr Zaker. Inequalities for the grundy chromatic number of graphs. Discret. Appl. Math., 155(18):2567–2572, 2007. doi:10.1016/J.DAM.2007.07.002.

[bib.bib1] [1] Pierre Aboulker, Édouard Bonnet, Eun Jung Kim, and Florian Sikora. Grundy coloring and friends, half-graphs, bicliques. Algorithmica, pages 1–28, 2022. doi:10.1007/S00453-022-01001-2.

[bib.bib2] [2] Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844–856, 1995. doi:10.1145/210332.210337.

[bib.bib3] [3] Júlio César Silva Araújo and Cláudia Linhares Sales. Grundy number on p ${}_{\mbox{4}}$ -classes. Electron. Notes Discret. Math., 35:21–27, 2009. doi:10.1016/J.ENDM.2009.11.005.

[bib.bib4] [4] R. Balakrishnan and T Kavaskar. Interpolation theorem for partial grundy coloring. Discrete Mathematics, 313(8):949–950, 2013. doi:10.1016/J.DISC.2013.01.018.

[bib.bib5] [5] Rangaswami Balakrishnan and T. Kavaskar. Color chain of a graph. Graphs Comb., 27(4):487–493, 2011. doi:10.1007/S00373-010-0989-7.

[bib.bib6] [6] Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Yota Otachi. Grundy distinguishes treewidth from pathwidth. In 28th Annual European Symposium on Algorithms (ESA 2020). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020.

[bib.bib7] [7] Édouard Bonnet, Florent Foucaud, Eun Jung Kim, and Florian Sikora. Complexity of grundy coloring and its variants. Discret. Appl. Math., 243:99–114, 2018. doi:10.1016/J.DAM.2017.12.022.

[bib.bib8] [8] Gregory J. Chaitin, Marc A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins, and Peter W. Markstein. Register allocation via coloring. Comput. Lang., 6(1):47–57, 1981. doi:10.1016/0096-0551(81)90048-5.

[bib.bib9] [9] CWK Chen and David YY Yun. Unifying graph-matching problem with a practical solution. In Proceedings of International Conference on Systems, Signals, Control, Computers, volume 55, 1998.

[bib.bib10] [10] C. A. Christen and S. M. Selkow. Some perfect coloring properties of graphs. Journal of Combinatorial Theory, Series B, 27(1):49–59, 1979. doi:10.1016/0095-8956(79)90067-4.

[bib.bib11] [11] Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 5. Springer, 2015. doi:10.1007/978-3-319-21275-3.

[bib.bib12] [12] Lyes Dekar, Brice Effantin, and Hamamache Kheddouci. An incremental distributed algorithm for a partial grundy coloring of graphs. In Ivan Stojmenovic, Ruppa K. Thulasiram, Laurence Tianruo Yang, Weijia Jia, Minyi Guo, and Rodrigo Fernandes de Mello, editors, Parallel and Distributed Processing and Applications, 5th International Symposium, ISPA 2007, Niagara Falls, Canada, August 29-31, 2007, Proceedings, volume 4742 of Lecture Notes in Computer Science, pages 170–181. Springer, 2007. doi:10.1007/978-3-540-74742-0_18.

[bib.bib13] [13] Reinhard Diestel. Graph theory, volume 173. Springer-Verlag Heidelberg, 2017.

[bib.bib14] [14] Irit Dinur, Elchanan Mossel, and Oded Regev. Conditional hardness for approximate coloring. SIAM J. Comput., 39(3):843–873, 2009. doi:10.1137/07068062X.

[bib.bib15] [15] B. Effantin, N. Gastineau, and O. Togni. A characterization of b-chromatic and partial grundy numbers by induced subgraphs. Discrete Mathematics, 339(8):2157–2167, 2016. doi:10.1016/J.DISC.2016.03.011.

[bib.bib16] [16] P. Erdös, S. T. Hedetniemi, R. C. Laskar, and G. C. E. Prins. On the equality of the partial grundy and upper ochromatic numbers of graphs. Discrete Mathematics, 272(1):53–64, 2003. doi:10.1016/S0012-365X(03)00184-5.

[bib.bib17] [17] P Fahad. Dynamic Programming using Representative Families. PhD thesis, Homi Bhabha National Institute, 2015.

[bib.bib18] [18] Uriel Feige and Joe Kilian. Zero knowledge and the chromatic number. J. Comput. Syst. Sci., 57(2):187–199, 1998. doi:10.1006/JCSS.1998.1587.

[bib.bib19] [19] Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM, 63(4):29:1–29:60, 2016. doi:10.1145/2886094.

[bib.bib20] [20] N. Goyal and S. Vishwanathan. Np-completeness of undirected grundy numbering and related problems. Unpublished manuscript, 1997.

[bib.bib21] [21] P. M. Grundy. Mathematics and games. Eureka, 2:6–9, 1939.

[bib.bib22] [22] András Gyárfás, Zoltán Király, and Jenö Lehel. On-line 3-chromatic graphs i. triangle-free graphs. SIAM J. Discret. Math., 12(3):385–411, 1999. doi:10.1137/S089548019631030X.

[bib.bib23] [23] F. Havet and L. Sampaio. On the grundy and b-chromatic numbers of a graph. Algorithmica, 65(4):885–899, 2013. doi:10.1007/S00453-011-9604-4.

[bib.bib24] [24] 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.

[bib.bib25] [25] Allen Ibiapina and Ana Silva. b-continuity and partial grundy coloring of graphs with large girth. Discrete Mathematics, 343(8):111920, 2020. doi:10.1016/J.DISC.2020.111920.

[bib.bib26] [26] Hal A. Kierstead and Karin Rebecca Saoub. First-fit coloring of bounded tolerance graphs. Discret. Appl. Math., 159(7):605–611, 2011. doi:10.1016/J.DAM.2010.05.002.

[bib.bib27] [27] Guy Kortsarz. A lower bound for approximating the grundy number. Discrete Mathematics & Theoretical Computer Science, 9, 2007.

[bib.bib28] [28] Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma, and Meirav Zehavi. Covering small independent sets and separators with applications to parameterized algorithms. ACM Transactions on Algorithms (TALG), 16(3):1–31, 2020. doi:10.1145/3379698.

[bib.bib29] [29] Dániel Marx. Graph colouring problems and their applications in scheduling. Periodica Polytechnica Electrical Engineering (Archives), 48(1-2):11–16, 2004.

[bib.bib30] [30] Dániel Marx. A parameterized view on matroid optimization problems. Theor. Comput. Sci., 410(44):4471–4479, 2009. doi:10.1016/J.TCS.2009.07.027.

[bib.bib31] [31] Moni Naor, Leonard J Schulman, and Aravind Srinivasan. Splitters and near-optimal derandomization. In Proceedings of IEEE 36th Annual Foundations of Computer Science, pages 182–191. IEEE, 1995. doi:10.1109/SFCS.1995.492475.

[bib.bib32] [32] B. S. Panda and Shaily Verma. On partial grundy coloring of bipartite graphs and chordal graphs. Discret. Appl. Math., 271:171–183, 2019. doi:10.1016/J.DAM.2019.08.005.

[bib.bib33] [33] L. Sampaio. Algorithmic aspects of graph colourings heuristics. PhD thesis, University Nice Sophia Antipolis, 2012.

[bib.bib34] [34] Z. Shi, W. Goddard, S. T. Hedetniemi, K. Kennedy, R. Laskar, and A. McRae. An algorithm for partial grundy number on trees. Discrete Mathematics, 304(1-3):108–116, 2005. doi:10.1016/J.DISC.2005.09.008.

[bib.bib35] [35] Zixing Tang, Baoyindureng Wu, Lin Hu, and Manouchehr Zaker. More bounds for the grundy number of graphs. J. Comb. Optim., 33(2):580–589, 2017. doi:10.1007/S10878-015-9981-8.

[bib.bib36] [36] Shaily Verma and B. S. Panda. Grundy coloring in some subclasses of bipartite graphs and their complements. Information Processing Letters, 163:105999, 2020. doi:10.1016/J.IPL.2020.105999.

[bib.bib37] [37] M. Zaker. Grundy chromatic number of the complement of bipartite graphs. Australasian Journal of Combinatorics, 31:325–330, 2005. URL: http://ajc.maths.uq.edu.au/pdf/31/ajc_v31_p325.pdf.

[bib.bib38] [38] M. Zaker. Results on the grundy chromatic number of graphs. Discrete mathematics, 306(23):3166–3173, 2006. doi:10.1016/J.DISC.2005.06.044.

[bib.bib39] [39] Manouchehr Zaker. Inequalities for the grundy chromatic number of graphs. Discret. Appl. Math., 155(18):2567–2572, 2007. doi:10.1016/J.DAM.2007.07.002.

Parameterized Saga of First-Fit and Last-Fit Coloring

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Our Results, Methods and Overview

Theorem 1.

Theorem 2 (Structural result).

Theorem 3.

Definition 4.

2 Preliminaries

Generic Notations.

3 FPT Algorithm for Partial Grundy Coloring

Observation 5.

Proof.

Definition 6.

Observation 7.

Observation 8 (♠).

3.1 Degree Reduction: Proof of Theorem 2

Lemma 9.

Proof of Theorem 2.

Overview of our algorithm.

Description of the algorithm.

Lemma 10.

Proof.

Claim 11.

Proof.

3.2 FPT Algorithm for Partial Grundy Coloring

Proposition 12 (Lemma 1.1. [28]).

Theorem 13.

Theorem 14.

Proof Sketch.

4 FPT Algorithm for Grundy Coloring on 𝑲𝒊,𝒋-free Graphs

Grundy Tree & Grundy Witness.

Observation 15 (♠).

Observation 16 (♠).

Definition 17.

Observation 18 (♠).

Observation 19 (♠).

Lemma 20.

Proof.

Lemma 21.

Proof.

Lemma 22.

Color Coding of 𝑮.

Grundy Representative Sets.

Definition 23.

Observation 24 (♠).

Observation 25 (♠).

Lemma 26.

Proof.

Lemma 27 (♠).

Some Useful Notations.

Description of the Algorithm.

Base Case.

Recursive Formula.

Lemma 28.

Proof.

References

Observation 8 ( $\spadesuit$ ).

4 FPT Algorithm for Grundy Coloring on $K_{i,j}$ -free Graphs

Observation 15 ( $\spadesuit$ ).

Observation 16 ( $\spadesuit$ ).

Observation 18 ( $\spadesuit$ ).

Observation 19 ( $\spadesuit$ ).

Color Coding of $𝑮$ .

Observation 24 ( $\spadesuit$ ).

Observation 25 ( $\spadesuit$ ).

Lemma 27 ( $\spadesuit$ ).