List Coloring Ordered Graphs with Forbidden Induced Subgraphs

Observe that every graph $H$ with one edge is an induced subgraph of , for some $\mathrm{\ell }\le |V(H)|$. Thus, it is sufficient to consider the case that $H=\text{<object type="image/svg+xml" data="dagpub-standalone-manual-2026-03-16-17-31-46-page-6.pdf2svg.svg" id="S3.SS1.SSS0.P0.SPx1.p1.m3.g1nest" class="ltx\_graphics ltx\_img\_landscape" width="38" height="12" style="width: 76px; height: unset; max-width: 100\%"></object>}$ . We can also assume that $\mathrm{\ell }\ge 1$, as for $\mathrm{\ell }=0$ the problem is trivial: all instances are edgeless.

We proceed by induction on $k$; the case $k\le 2$ is obvious. Thus suppose that $k\ge 3$ and the claim holds for $k-1$. Let $(G,L)$ be an $n$-vertex instance of List $k$-Coloring such that $G$ is an -free ordered graph.

We first verify if there is a list coloring $c:(G,L)\to [k]$ such that some color $i\in [k]$ is used on at most $2\mathrm{\ell }-1$ vertices; for every $i\in [k]$, and for every $A_i\subseteq V(G)$ of size at most $2\mathrm{\ell }-1$, we create an instance $(G_1,L_1)$ from $(G,L)$ as follows:

1. 1.

   for every $v\in A_i$, we remove from $L(v)$ all colors but $i$,

2. 2.

   for every $v\in V(G)\setminus A_i$, we set its list to $L(v)\setminus \{i\}$,

3. 3.

   we exhaustively apply reduction rules (R1) and (R2).

Note that now $(G_1,L_1)$ can be seen as an instance of List $(k-1)$-Coloring, and thus, it can be solved in polynomial time by the inductive assumption.

So since now we can assume that for every list coloring $c:(G,L)\to [k]$, every color $i\in [k]$ is used on at least $2\mathrm{\ell }$ vertices. Now we branch on the choice of first and last $\mathrm{\ell }$ vertices in each color, i.e., for every $(2k)$-tuple $𝖠=(A_1,\mathrm{\dots },A_k,B_1,\mathrm{\dots },B_k)$ of pairwise disjoint sets, each of size $\mathrm{\ell }$, where $A_i$ precedes $B_i$, we create from $(G,L)$ an instance $(G_{𝖠},L_{𝖠})$ as follows:

1. 1.

   for every $i\in [k]$, for $v\in A_i\cup B_i$, we remove from $L(v)$ all colors but $i$,

2. 2.

   for every $i\in [k]$, for every $v\in V(G)\setminus (A_i\cup B_i)$, if $v$ precedes the last vertex of $A_i$ or the first vertex of $B_i$ precedes $v$, then we remove $i$ from $L(v)$,

3. 3.

   we exhaustively apply reduction rules.

Consider such an instance $(G_{𝖠},L_{𝖠})$. Let $i\in [k]$, and let $X_i$ be the set of vertices $v$ in $G_{𝖠}$ with $i\in L_{𝖠}(v)$.

So since now, we assume that we are dealing with an instance that satisfies the property from Claim 4. For simplicity, let us denote the current instance $(G,L)$, omitting the subscript $𝖠$.

Let $v_1\prec \mathrm{\dots }\prec v_n$ denote the vertices of $G$. Moreover, for $j\in [n]$, we define $V_j=\{v_1,\mathrm{\dots },v_j\}$. Let $j\in [n]$, let ${𝒞}_j$ denote the family of all $k$-tuples of pairwise disjoint independent subsets of $V_j$, each of size at most $\mathrm{\ell }$. We say that a list coloring $c:(G[V_j],L)\to [k]$ is compatible with $(C_1,\mathrm{\dots },C_k)\in {𝒞}_j$ if, for every $i\in [k]$, the following hold: if $|C_i|\le \mathrm{\ell }-1$, then $c^{-1}(i)=C_i$, and if $|C_i|=\mathrm{\ell }$, then $C_i$ is the set of $\mathrm{\ell }$ last vertices of $V_j$ colored with $i$.

For every $j\in [n]$, we will construct a table ${\mathrm{𝖳𝖺𝖻}}_j$ of entries, indexed by all elements of ${𝒞}_j$; note that the total size of of all tables is bounded by $n\cdot n^{kw}$. We will set ${\mathrm{𝖳𝖺𝖻}}_j[(C_1,\mathrm{\dots },C_k)]$ to true if and only if there exists a list coloring of $(G[V_j],L)$ that is compatible with $(C_1,\mathrm{\dots },C_k)$. Clearly, $(G,L)$ is a yes-instance of List $k$-Coloring if and only if ${\mathrm{𝖳𝖺𝖻}}_n$ contains at least one true entry. So it remains to show how to compute the entries efficiently.

First, we set ${\mathrm{𝖳𝖺𝖻}}_1[C_1,\mathrm{\dots },C_k]$ to true if and only if there is $i\in L(v_1)$ such that $C_i=\{v_1\}$ and $C_t=\mathrm{\varnothing }$ for $t\ne i$. So now assume that $j\ge 2$, we computed all entries for ${\mathrm{𝖳𝖺𝖻}}_{j-1}$, and let $(C_1,\mathrm{\dots },C_k)\in {𝒞}_j$. If there is no $t\in L(v_j)$ such that $v_j\in C_t$, we set ${\mathrm{𝖳𝖺𝖻}}_j[C_1,\mathrm{\dots },C_k]$ to false. So now assume that such $t$ exists; clearly it is unique. We set ${\mathrm{𝖳𝖺𝖻}}_j[(C_1,\mathrm{\dots },C_k)]$ to true if and only if at least one of following conditions is satisfied.

1. 1.

   ${\mathrm{𝖳𝖺𝖻}}_{j-1}[(C_1,\mathrm{\dots },C_t\setminus \{v_j\},\mathrm{\dots },C_k)]$ is true.

2. 2.

   $|C_t|=\mathrm{\ell }$ and there exists $x\in V_{j-1}$ such that: (i) $x$ precedes all the vertices of $C_t$, (ii) $x$ is non-adjacent to $C_t$, and (iii) for $C_t^{\prime }=C_t\setminus \{v_j\}\cup \{x\}$, we have that ${\mathrm{𝖳𝖺𝖻}}_{j-1}[(C_1,\mathrm{\dots },C_{t-1},C_t^{\prime },C_{t+1},\mathrm{\dots },C_k)]$ is true.

Clearly, all table entries can be computed in polynomial time in $n$.

The full proof of the correctness can be found in the full version of the paper ($\mathrm{♠}$). Let us only mention how we use -freeness here. In general, it might happen that for some $j$, there exists $x\in V_{j-1}$ such that $C_t\cup \{x\}$ is an independent set and there is a coloring $c$ of $V_{j-1}$ compatible with $(C_1,\mathrm{\dots },C_{t-1},C_t\setminus \{v_j\}\cup \{x\},C_{t+1},\mathrm{\dots },C_k)$, but such a coloring cannot be extended to $V_j$ by $c(v_j)=t$ since there is some neighbor $y$ of $v_j$ such that $c(y)=t$. In our case, existence of such a vertex $y$ yields an induced copy of on vertices of $X_t$, which contradicts Claim 4. This completes the proof. $◀$

Let $G$ be an ordered $n$-vertex ${}_{\mathrm{\ell }}{}^{}\text{<object type="image/svg+xml" data="dagpub-standalone-manual-2026-03-16-17-31-46-page-3.pdf2svg.svg" id="S3.SS2.SSS0.P0.SPx1.p1.m3.g1nest" class="ltx\_graphics ltx\_img\_landscape" width="19" height="5" style="width: 38px; height: unset; max-width: 100\%"></object>}$-free graph, given with a list function $L:V(G)\to 2^{[4]}$. We start with checking if $G$ contains a $K_5$ and, if so, we immediately reject the instance. This can be done in polynomial time by brute force.

First, suppose there is a list 4-coloring of $G$ such that for some $i\in [4]$, at most $\mathrm{\ell }-1$ vertices receive color $i$. We might exhaustively guess such an $i$ and the set of vertices colored $i$, remove them from the graph, and remove $i$ from the lists of all remaining vertices. This way we reduced the problem to solving a polynomial number of instances of List 3-Coloring, each of which can be solved in polynomial time by using the result of Hajebi et al. [13, Theorem 22], mentioned in Table 1.

So, from now on let us focus on looking for a list 4-coloring, where each color appears at least $\mathrm{\ell }$ times. The algorithm consists of four main phases.

For each $i\in [4]$, we exhaustively guess the first $\mathrm{\ell }$ vertices that will receive color $i$. More precisely, for every 4-tuple $𝒜=(A_1,A_2,A_3,A_4)$ of pairwise disjoint independent sets, each of size $\mathrm{\ell }$, we create an instance as follows.

1. 1.

   For every $i\in [4]$ and every vertex $v\in A_i$, we set the list of $v$ to $L(v)\cap \{i\}$.

2. 2.

   For every $i\in [4]$, we remove $i$ from lists of all vertices not in $A_i$ that precede the last vertex of $A_i$.

3. 3.

   We exhaustively apply reduction rules.

Observe that as we assumed that in any list 4-coloring of $G$ there are at least $\mathrm{\ell }$ vertices in each color, $(G,L)$ is a yes-instance if and only if at least one of the created instances is a yes-instance. Furthermore, the number of branches in Phase 1 is at most $n^{4\mathrm{\ell }}$, which is polynomial. Consider one such branch for $𝒜=(A_1,A_2,A_3,A_4)$ and let $(G_1,L_1)$ be the current instance. Before we proceed to Phase 2, let us analyze the properties of $(G_1,L_1)$.

Let us classify forward neighbors of a vertex $v$. We say that a forward neighbor $u$ of $v$ is safe (in $(G_1,L_1)$) if $L_1(u)\cap L_1(v)\ne \mathrm{\varnothing }$, and otherwise it is dangerous. Now, for every vertex we can bound the number of its safe forward neighbors.

We say that a vertex $v$ is bad if it has at least $3\mathrm{\ell }+4$ dangerous forward neighbors. If $v$ is not bad, then it is good. Let $\mathrm{𝖡𝖺𝖽}$ and $\mathrm{𝖦𝗈𝗈𝖽}$ denote, respectively, the sets of bad and good vertices.

Let us make a few comments about bad and good vertices. First, every $v\in \mathrm{𝖡𝖺𝖽}$ has list of size $2$. Indeed, the reduction rules assert that there are no vertices with lists of size at most one, and if the list of $v$ has at least three elements, then there are no vertices with lists disjoint with $L_1(v)$ (and in particular $v$ has no dangerous forward neighbors). Second, for analogous reasons, all dangerous forward neighbors of a bad vertex $v$ have the same list, i.e., $[4]\setminus L_1(v)$. Finally, if $v$ is good, ˜7 implies that $v$ has at most $12+(3\mathrm{\ell }+3)=3\mathrm{\ell }+15$ forward neighbors.

We proceed further with the instance $(G_1,L_1)$. We consider two cases depending on the size of $\mathrm{𝖦𝗈𝗈𝖽}$. First, if , then we can exhaustively guess coloring on $\mathrm{𝖦𝗈𝗈𝖽}$. More precisely, for each $c:\mathrm{𝖦𝗈𝗈𝖽}\to [4]$ we create a corresponding instance by setting the list of every $v\in \mathrm{𝖦𝗈𝗈𝖽}$ to $L_1(v)\cap \{c(v)\}$ and then exhaustively applying reduction rules.

The number of instances created this way is at most $4^{\mathrm{𝖱𝖺𝗆}(5,\mathrm{\ell })-1}$, which is a constant as $\mathrm{\ell }$ is fixed. Since every bad vertex has list of size $2$, in any produced instance, every vertex must have a list of size $2$. Here we emphasize that the vertices in the newly created instances might become good, but they were bad before the guessing and their lists could only shrink. Therefore, applying Theorem 2, we can solve each instance in polynomial time. This completes the proof in this case.

So since now, we can assume that $|\mathrm{𝖦𝗈𝗈𝖽}|\ge \mathrm{𝖱𝖺𝗆}(5,\mathrm{\ell })$. Let $D$ be the set of first $\mathrm{𝖱𝖺𝗆}(5,\mathrm{\ell })$ good vertices. We exhaustively guess the coloring of $D\cup N^{+}(D)$, i.e., for every $c:D\cup N^{+}(D)\to [4]$, we create a corresponding instance by setting the list of every $v\in D\cup N^{+}(D)$ to $L_1(v)\cap \{c(v)\}$ and applying reduction rules exhaustively.

Recall that every good vertex has at most $3\mathrm{\ell }+15$ forward neighbors, and thus the size of $D\cup N^{+}(D)$ is bounded by $|D|+|D|\cdot (3\mathrm{\ell }+15)=\mathrm{𝖱𝖺𝗆}(5,\mathrm{\ell })\cdot (3\mathrm{\ell }+16)$. Therefore, the number of instances created in Phase 2 is at most $4^{\mathrm{𝖱𝖺𝗆}(5,\mathrm{\ell })\cdot (3\mathrm{\ell }+16)}$, which is again constant for fixed $\mathrm{\ell }$.

Consider one such instance and denote it by $(G_2,L_2)$. We partition the vertex set of $G_2$ into sets $P,S$ called prefix and suffix so that in $P$ are all vertices that in $G_1$ precede the last vertex of $D$, and $S$ contains the remaining vertices of $G_2$. Observe that all vertices in $P$ were bad at the end of Phase 1, i.e., before we guessed a coloring on $D\cup N^{+}(D)$. In the instance $(G_2,L_2)$ they do not have to be bad, but we do not care if they are bad now. We will only use the facts that (i) they have lists of size 2 and (ii) ˜8 holds for all vertices of $P$. Indeed, note that reduction rules did not increase the size of lists or the number of non-neighbors.

Moreover, observe that the graph induced by $S$ is -free. Indeed, since all vertices of $S$ were not removed by reduction rules applied after the branching in Phase 2, there are no edges between $D$ and $S$. Moreover, since $G$ has no $K_5$, there is an independent set $D^{\prime }\subseteq D$ of size $\mathrm{\ell }$. Consequently, if $G[S]$ contained an induced , then, together with $D^{\prime }$, it would form an induced ${}_{\mathrm{\ell }}{}^{}\text{<object type="image/svg+xml" data="dagpub-standalone-manual-2026-03-16-17-31-46-page-3.pdf2svg.svg" id="S3.SS2.SSS0.P0.SPx3.p6.m13.g1nest" class="ltx\_graphics ltx\_img\_landscape" width="19" height="5" style="width: 38px; height: unset; max-width: 100\%"></object>}$ in $G$, a contradiction. We proceed to the third phase.

Let $(G_2,L_2)$ be an instance produced in Phase 2. For $X\in \left(\genfrac{}{}{0pt}{}{[4]}{2}\right)$, by $P_X$ we denote the set of vertices of $P$ with list $X$; recall that each vertex of $P$ is bad and thus has list of size $2$. If, for some $X$, the set $P_X$ does not induce a bipartite graph, we can immediately terminate the current call and reject. So assume that, for each $X$, the graph $G[P_X]$ is bipartite. We consider two cases.

If , then we exhaustively guess the coloring of $P_X$, i.e., for every $c:P_X\to X$, we create a corresponding instance by setting the list of every $v\in P_X$ to $L_2(v)\cap \{c(v)\}$ and applying reduction rules exhaustively. The number of instances created in this case is at most $2^{2\mathrm{\ell }-1}$, i.e., a constant.

Now let us assume that $|P_X|\ge 2\mathrm{\ell }$. Denote $X=\{i,j\}$, and suppose that we are dealing with a yes-instance, i.e., there is a coloring $c$ of $G_2$ respecting lists $L_2$. Observe that one of the following holds.

1. (C1)

   For some $\iota \in \{i,j\}$, at most $\mathrm{\ell }-1$ vertices of $P_X$ receive color $\iota$ in $c$.

2. (C2)

   Each of colors $i,j$ appears at least $\mathrm{\ell }$ times on $P_X$ in $c$.

We create the following instances, corresponding to the cases above.

1. (I1)

   For every $\iota \in X$ and every set $U\subseteq P_X$ of size at most $\mathrm{\ell }-1$, we create a corresponding instance by setting the list of every vertex $v\in U$ to $L_2(v)\cap \{\iota \}$, and the list of every vertex $v\in P_X\setminus U$ to $L_2(v)\setminus \{\iota \}$.

2. (I2)

   For every pair $(U_{X,i},U_{X,j})$, where $U_{X,i},U_{X,j}$ are disjoint independent sets contained in $P_X$, each of size $\mathrm{\ell }$, we create a corresponding instance in the following way: (i) for every vertex $v\in U_{Xi}$, we set its list to $L_2(v)\cap \{i\}$, (ii) for every vertex $v\in U_{X,j}$, we set its list to $L_2(v)\cap \{j\}$, and (iii) for every vertex $u$ of $P_X\setminus U_{X,i}$ preceding the last vertex of $U_{X,i}$, we remove $i$ from $L_2(u)$, and (iv) and for every vertex $u$ of $P_X\setminus U_{X,j}$ preceding the last vertex of $U_{X,j}$, we remove $j$ from $L_2(u)$.

We exhaustively apply reduction rules to all created instances. The number of instances created in this case is at most $n^{2\mathrm{\ell }}$.

The intended role of the set $U_{X,i}$ (resp., $U_{X,j}$) in (I2) is that it contains the first $\mathrm{\ell }$ vertices of $P_X$ colored $i$ (resp., $j$). If $(G_2,L_2)$ is a yes-instance, and there is coloring satisfying (C1), then at least one of the instances created in (I1) is a yes-instance, and if there is a coloring satisfying (C2), then at least one of the instances created in (I2) is a yes-instance. Thus, if $(G_2,L_2)$ is a yes-instances, then at least one of the instances created in Phase 3 is a yes-instance. The total number of instances created in this phase is at most $\left(\genfrac{}{}{0pt}{}{4}{2}\right)\cdot n^{2\mathrm{\ell }}$, i.e., polynomial in $n$.

Let us analyze an instance $(G_3,L_3)$ created in Phase 3. Recall that all vertices of $P\cap V(G_3)$ have lists of size 2.

We proceed to Phase 4. We emphasize that sets $P$ and Good are not redefined with respect to the current instance.

Let $(G_3,L_3)$ be an instance given by Phase 3. By ˜9, there are at most two distinct lists on $P\cap V(G_3)$, and by symmetry, we can assume that every vertex of $P$ in $(G_3,L_3)$ has list either $\{1,2\}$ or $\{3,4\}$. Furthermore, if for $X=\{i,j\}\in \{\{1,2\},\{3,4\}\}$, we have $P_X\cap V(G_3)\ne \mathrm{\varnothing }$, then $(G_3,L_3)$ corresponds to a branch of type (I1), i.e., a branch for the sets $U_{X,i},U_{X,j}$. Let $Y$ be the set of vertices in $G_3$ that consists of safe forward neighbors of $U_{\{1,2\},1}$ (if $P_{\{1,2\}}\cap V(G_3)\ne \mathrm{\varnothing }$) and safe forward neighbors of $U_{\{3,4\},3}$ (if $P_{\{3,4\}}\cap V(G_3)\ne \mathrm{\varnothing }$).

For every $c:Y\to [4]$, we create a corresponding instance as follows:

1. 1.

   for every $v\in Y$, we set the list of $v$ to $L_3(v)\cap \{c(v)\}$,

2. 2.

   we exhaustively apply reduction rules,

3. 3.

   we remove all edges whose one endpoint has list $\{1,2\}$ and the other $\{3,4\}$, and at least one endpoint is in $P$.

By ˜7, each vertex has at most 12 safe forward neighbors and thus, we guess a coloring on at most $12\cdot 2\mathrm{\ell }=24\mathrm{\ell }$ vertices. Therefore, the number of instances created in this phase is at most $4^{24\mathrm{\ell }}$. Note that the edges removed in the final step do not matter for coloring, so we obtain an equivalent instance. Let $(G_4,L_4)$ be an instance obtained in this phase. We point out that in general, if we remove edges in a (ordered) graph which is $F$-free for some graph $F$, it does not have to stay $F$-free. However, in our case, we will show that the resulting graph is even -free.

Summing up, the instances obtained in Phase 4 are -free and thus chordal. Chordal graphs of bounded clique number have bounded treewidth, and thus, each obtained instance can be solved in polynomial time by standard dynamic programming on tree decomposition (see for example [6]). This completes the proof. $◀$

Let us conclude this section with brief discussion why the approach from Theorem 5 fails for more than 4 colors. In general, in List $k$-Coloring, it is beneficial if adjacent vertices have intersecting lists. This way deciding on a color of one vertex allows to shrink the list of the other, see e.g. [18, 1]. On the other hand, adjacent vertices with disjoint lists of size at least 2 often appear in hardness proofs of List k-Coloring for $k\ge 4$, see Section 4 or, e.g., [1].

In the proof of Theorem 5, we called (forward) neighbors of $v$ with list disjoint from $L(v)$ dangerous and dealing with them was the most technically involved part of the argument. The crucial property that was very useful here is that every dangerous forward neighbor of $v$ has the same list, i.e., $[4]\setminus L(v)$. This enforces many constraints on possible lists of vertices.

Already for List 5-Coloring, a vertex $v$ can have several types of forward neighbors with list disjoint from $L(v)$, and this is the main obstacle in generalizing our approach to more than 4 colors.