betaFeedback

WorksComputer Science

List 3-Coloring in tame classes of graphs in quasipolynomial time

Abstract

A class of graphs G\mathcal{G} is tame if there is a constant c such that every nn-vertex graph in G\mathcal{G} has at most ncn^c minimal separators. Many important graph classes are tame, including chordal graphs, permutation graphs, and circle graphs. Several fundamental problems, most notably Max Weight Independent Set, can be solved in polynomial time on every tame class, which explains in a unified way their tractability on all these classes. We show that List 3-Coloring can be solved in quasipolynomial time on every tame class of graphs.

Introduction

A central theme in algorithmic graph theory is to understand how the complexity of computationally hard problems changes when the input graph is restricted to a specific graph class. For many classical problems, this has led to a large number of results, each exploiting the structure of a particular class. It is therefore very desirable to have unifying frameworks that explain the tractability of a problem in many classes at once.

One such framework is given by the notion of tame classes. Following the nomenclature of [19, 20, 27], a class G\mathcal{G} of graphs is tame (resp., quasitame) if there is a constant cc (resp., two constants aa and cc) such that every nn-vertex graph in G\mathcal{G} has at most ncn^c (resp., 2clog⁡an2^{c\log^a n}) minimal separators. Understanding which graph classes are (quasi)tame has recently attracted significant attention [1, 16, 19, 20, 27]. Many important graph classes are tame, including chordal graphs [31], weakly chordal graphs [7], circular-arc graphs [25], and circle graphs [25], which in turn include permutation graphs.

Bouchitté and Todinca [7, 8] introduced a general framework based on so-called potential maximal cliques. It was used to solve Max Weight Independent Set (MWIS) [15], and later extended by Fomin, Todinca, and Villanger [14] to the (tw⁡≤r,ψ)(\operatorname{tw} \le r,\psi)-MWIS problem. Here, rr is a fixed integer and ψ\psi is a fixed formula of counting monadic second-order logic (CMSO2_2), and, given a graph GG with weights on vertices, we look for a maximum-weight set X⊆V(G)X \subseteq V(G) such that G[X]G[X] has treewidth at most rr and satisfies ψ\psi.1 This captures many problems, for example MWIS (for r=0r=0) and Feedback Vertex Set (for r=1r=1), as the complement of a minimum-weight feedback vertex set is a maximum-weight induced forest.

Theorem 1.1 ([7, 8, 14]). For every fixed integer rr and CMSO2_2 formula ψ\psi, the (tw⁡≤r,ψ)(\operatorname{tw} \le r,\psi)-MWIS problem can be solved in time polynomial in the number of vertices and the number of minimal separators of the input graph.

Consequently, (tw⁡≤r,ψ)(\operatorname{tw} \le r,\psi)-MWIS can be solved in polynomial time on every tame class, and in quasipolynomial time on every quasitame class. Are there any other natural problems that can be solved in polynomial time on every tame class?

A hint comes from the study of PtP_t-free graphs, i.e., graphs that do not contain the tt-vertex path PtP_t as an induced subgraph. Already P5P_5-free graphs are not tame: the graph consisting of two nn-vertex cliques with a perfect matching between them is P5P_5-free and has 2n−22^n-2 minimal separators [29]. Nevertheless, MWIS and, more generally, (tw⁡≤r,ψ)(\operatorname{tw} \le r,\psi)-MWIS can be solved in polynomial time in P5P_5-free graphs [2, 26] and in P6P_6-free graphs [11, 22], using relaxations of the framework of potential maximal cliques. Moreover, for every fixed tt, these problems can be solved in quasipolynomial time in PtP_t-free graphs [18, 21, 28]. While this is weaker than polynomial-time solvability, it is a strong indication that these problems are not NP-hard in PtP_t-free graphs: otherwise, every problem in NP could be solved in quasipolynomial time.

Another problem whose complexity in PtP_t-free graphs is similar to that of MWIS is List 3-Coloring. Here we are given a graph GG and a list assignment LL that assigns to every vertex v∈V(G)v \in V(G) a list L(v)⊆{1,2,3}L(v) \subseteq\{1,2,3\} of colors, and we ask whether there is a proper coloring of GG that respects LL, i.e., every vertex receives a color from its list. List 3-Coloring can be solved in polynomial time in PtP_t-free graphs for t≤7t \le7 [6], and in quasipolynomial time for every fixed tt [28].

Turning back to tame classes, List 3-Coloring can be solved in polynomial time in some of them, but using class-specific arguments [9, 13, 24, 30, 34]. Can we obtain such a result in a unified way, as for MWIS in Theorem 1.1?

Question 1.2. Can List 3-Coloring be solved in polynomial time on every tame class of graphs?

We remark that analogous questions for some closely related problems have negative answers, unless P=NP\mathrm{P}=\mathrm{NP}: 4-Coloring is NP-hard in circle graphs [32], List 4-Coloring is NP-hard in chordal bipartite graphs [23], which are tame as they are weakly chordal, and Odd Cycle Transversal is NP-hard in P6P_6-free graphs of clique number at most 3 [10, 12], which form a tame class [29].

Let us mention an important special case of Question 1.2, namely circle graphs, i.e., intersection graphs of chords of a circle. Unger [33] claimed a polynomial-time algorithm for 3-Coloring circle graphs, but only an extended abstract was published, and the proof was believed to be flawed. Recently, Bachmann, Rutter, and Stumpf [4] exposed mistakes in the algorithm and argued that the problem should be considered open. Very recently, Ajaykrishnan E S, Ganian, Lokshtanov, and Surianarayanan [3] gave an algorithm for List 3-Coloring in circle graphs with running time nO(log⁡n)n^{\mathcal{O}(\log n)}.

Another special case of Question 1.2 was explicitly asked by Huang, Johnson, and Paulusma [23]: what is the complexity of List 3-Coloring in chordal bipartite graphs?

In this paper we give a partial answer to Question 1.2.

Theorem 1.3. List 3-Coloring can be solved in quasipolynomial time on every quasitame class of graphs. For tame classes, the running time is nO(log⁡5n)n^{\mathcal{O}(\log^{5} n)}, where nn is the number of vertices in the input graph.

In particular, Theorem 1.3 generalizes the result of [3] to all tame classes, albeit with a worse running time, and gives a quasipolynomial-time algorithm for List 3-Coloring in chordal bipartite graphs, partially answering the question of Huang et al. [23].

Technical overview. Let us present a high-level overview of the algorithm behind Theorem 1.3. Let (G,L)(G,L) be an instance of List 3-Coloring, where GG has nn vertices and fewer than 2k2^{k} minimal separators; for tame classes, k=O(log⁡n)k=\mathcal{O}(\log n). We branch into nO(k2log⁡2n)n^{\mathcal{O}(k^{2}\log^{2} n)} instances, obtained by deleting vertices and removing colors from lists, such that (G,L)(G,L) is a yes-instance if and only if one of them is, and every component of each of them has at most n/2n/2 vertices. Then we recurse on the components.

The branching scheme is inspired by the work of Gartland and Lokshtanov [18, 20]. They showed that there is a set DD of at most 2k2k vertices such that every component of G−N[D]G-N[D] has at most n/2n/2 vertices, where N[D]N[D] consists of DD and its neighbors [20]. We guess the coloring of DD and delete DD; afterwards, every remaining neighbor of DD has at most two colors in its list. Repeating this and using a potential-function argument, we obtain O(log⁡n)\mathcal{O}(\log n) such sets D1,…,DhD_1,\ldots,D_h with no edges between them, such that no vertex is adjacent to all of them. Let SiS_i be the set of neighbors of DiD_i. By another result of Gartland and Lokshtanov [20], if for all i≠ji\ne j no component of G−(Si∩Sj)G-(S_i\cap S_j) contained vertices of both Si∖SjS_i\setminus S_j and Sj∖SiS_j\setminus S_i, then every component of GG would have at most n/2n/2 vertices.

The main new ingredient is a way to ensure this condition, i.e., to destroy all paths from DiD_i to DjD_j that avoid Si∩SjS_i\cap S_j, by deleting vertices from the instance. More generally, let AA and BB be sets at distance at least 33 such that G[A∪B]G[A\cup B] has cc components. The paths of length 33 from AA to BB correspond to edges xyxy with xx adjacent to AA and yy adjacent to BB, and in every proper coloring, the vertices not colored ii cover all such edges, for each color ii. The inclusion-minimal sets covering these edges are inclusion-minimal sets separating AA from BB in an induced subgraph of GG, so each of them is the union of fewer than cc minimal separators, and there are at most 2kc2^{kc} of them. Guessing one such set for each color and removing the color from its vertices, we ensure that one endpoint of each such edge is left with at most one color, and can be deleted. This increases the distance between AA and BB to 44, and a similar step increases it to 55. Then no vertex is at distance at most 22 from both AA and BB, which allows us to recurse on a problem where only half of the vertices may serve as internal vertices of the paths.

Preliminaries

All logarithms are binary, and for a positive integer nn, we write [n]={1,…,n}[n]=\{1,\ldots,n\}.

Graph theory. All graphs considered in this paper are finite and simple. Let GG be a graph. For a vertex vv, the neighborhood NG(v)N_G(v) of vv is the set of neighbors of vv, and the closed neighborhood of vv is NG[v]=NG(v)∪{v}N_G[v]=N_G(v)\cup\{v\}. For a set X⊆V(G)X\subseteq V(G), the neighborhood NG(X)N_G(X) of XX is the set of vertices outside XX that have a neighbor in XX, and the closed neighborhood of XX is NG[X]=X∪NG(X)N_G[X]=X\cup N_G(X). We omit the subscript if the graph is clear from the context. By G[X]G[X] we denote the subgraph of GG induced by XX, and for any set XX we write G−XG-X for G[V(G)∖X]G[V(G)\setminus X]. A component of GG is a maximal connected subgraph of GG, and cc⁡(G)\operatorname{cc}(G) denotes the number of components of GG. A set X⊆V(G)X \subseteq V(G) is independent if no edge of GG has both endpoints in XX, and it is a vertex cover of GG if every edge of GG has an endpoint in XX. Thus XX is independent if and only if V(G)∖XV(G) \setminus X is a vertex cover of GG. A vertex cover is minimal if no proper subset of it is a vertex cover. Two disjoint sets X,Y⊆V(G)X,Y \subseteq V(G) are anticomplete if there is no edge between XX and YY; we also say that XX is anticomplete to YY.

We denote a path by the sequence v0v1…vmv_0v_1\ldots v_m of its vertices; the vertices v0v_0 and vmv_m are its endpoints, and the other vertices are internal. The length of a path is the number of its edges. For a vertex vv and a set A⊆V(G)A \subseteq V(G), the distance between vv and AA in GG is the minimum length of a path in GG from vv to a vertex of AA, or ∞\infty if there is no such path; in particular, it is 00 if v∈Av \in A. For disjoint sets A,B⊆V(G)A,B \subseteq V(G), an AA-BB-path is a path with one endpoint in AA, the other endpoint in BB, and all internal vertices outside A∪BA \cup B. By dist⁡G(A,B)\operatorname{dist}_G(A,B) we denote the minimum length of an AA-BB-path in GG, or ∞\infty if there is no such path. Note that dist⁡G(A,B)\operatorname{dist}_G(A,B) is the minimum distance between a vertex of BB and AA. For pairwise disjoint sets A,B,Z⊆V(G)A,B,Z \subseteq V(G), an AA-BB-path in GG through ZZ is an AA-BB-path in GG all of whose internal vertices belong to ZZ. The distance between AA and BB through ZZ, denoted by dist⁡G(A,B∣Z)\operatorname{dist}_G(A,B \mid Z), is the minimum length of an AA-BB-path in GG through ZZ, or ∞\infty if there is no such path. Equivalently, dist⁡G(A,B∣Z)=dist⁡G[A∪B∪Z](A,B)\operatorname{dist}_G(A,B \mid Z) = \operatorname{dist}_{G[A\cup B\cup Z]}(A,B). Note that if Z′⊆ZZ' \subseteq Z, then dist⁡G(A,B∣Z′)≥dist⁡G(A,B∣Z)\operatorname{dist}_G(A,B \mid Z') \ge\operatorname{dist}_G(A,B \mid Z).

List 3-Coloring. Consider an instance (G,L)(G,L) of List 3-Coloring. We say that (G′,L′)(G',L') is a subinstance of (G,L)(G,L) if G′G' is an induced subgraph of GG and L′(v)⊆L(v)L'(v) \subseteq L(v) for every v∈V(G′)v \in V(G'). A family I\mathcal{I} of subinstances of (G,L)(G,L) is equivalent to (G,L)(G,L) if (G,L)(G,L) is a yes-instance if and only if at least one instance in I\mathcal{I} is a yes-instance. Note that a subinstance of a subinstance of (G,L)(G,L) is a subinstance of (G,L)(G,L). Consequently, equivalence is transitive: if I\mathcal{I} is equivalent to (G,L)(G,L), and for every (G′,L′)∈I(G',L') \in\mathcal{I} the family I(G′,L′)\mathcal{I}_{(G',L')} of subinstances of (G′,L′)(G',L') is equivalent to (G′,L′)(G',L'), then ⋃(G′,L′)∈II(G′,L′)\bigcup_{(G',L')\in\mathcal{I}}\mathcal{I}_{(G',L')} is equivalent to (G,L)(G,L).

We consider the following two reduction rules for List 3-Coloring.

(R1) If there is a vertex with an empty list, then (G,L)(G,L) is a no-instance.

(R2) If there is a vertex vv with ∣L(v)∣=1|L(v)| = 1, then remove the unique color in L(v)L(v) from the lists of neighbors of vv, and remove vv.

Their correctness is straightforward, and they can be applied in polynomial time. An instance (G,L)(G,L) is reduced if none of the above rules can be applied to it.

Minimal separators. For two disjoint sets A,B⊆V(G)A,B \subseteq V(G), a set S⊆V(G)∖(A∪B)S \subseteq V(G) \setminus(A \cup B) is an AA-BB-separator if no component of G−SG-S contains vertices from both AA and BB. A set SS is a minimal AA-BB-separator if it is an AA-BB-separator and no proper subset of SS is an AA-BB-separator. For distinct vertices u,v∈V(G)u,v \in V(G), we write uu-vv-separator instead of {u}\{u\}-{v}\{v\}-separator. A minimal separator in GG is a set that is a minimal uu-vv-separator for some u,v∈V(G)u,v \in V(G). By μ(G)\mu(G) we denote the number of minimal separators in GG. One can readily verify (see e.g. [19 p. 3064]) that if G′G' is an induced subgraph of GG, then μ(G′)≤μ(G)\mu(G') \le\mu(G).

Theorem 2.1 (Berry, Bordat, Cogis [5]). *Given a graph GG, all its minimal separators can be enumerated in time ∣V(G)∣O(1)⋅(μ(G)+1)|V(G)|^{O(1)} \cdot(\mu(G)+1).

Balanced separators. For δ∈(0,1)\delta\in(0,1), a set S⊆V(G)S \subseteq V(G) is a δ\delta-balanced separator in GG if every component of G−SG-S has at most δ∣V(G)∣\delta|V(G)| vertices.

Lemma 2.2 (Gartland, Lokshtanov [20]). Let k≥1k \ge1 be an integer, and let GG be a graph with μ(G)<2k\mu(G) < 2^k. Then there is a set D⊆V(G)D \subseteq V(G) of size at most 2k2k such that N[D]N[D] is a 12\frac{1}{2}-balanced separator.

We remark that Lemma 2.2 follows from combining two results: that every graph that contains a so-called kk-creature has at least 2k2^k minimal separators [17 Lemma 7.6.18], and that every graph that does not contain a kk-creature admits a balanced separator dominated by at most 2k2k vertices [17 Lemma 7.4.7].

We say that two sets S1,S2⊆V(G)S_1,S_2 \subseteq V(G) are crossing in GG if there is a component of G−(S1∩S2)G-(S_1 \cap S_2) that intersects both S1∖S2S_1 \setminus S_2 and S2∖S1S_2 \setminus S_1. Otherwise, S1S_1 and S2S_2 are non-crossing.

Theorem 2.3 (Gartland, Lokshtanov [20]). Let GG be a graph, let δ∈(0,1)\delta\in(0,1), and let S\mathcal{S} be a family of pairwise non-crossing δ\delta-balanced separators in GG such that no vertex of GG belongs to all sets in S\mathcal{S}. Then every component of GG has at most δ∣V(G)∣\delta|V(G)| vertices.

Separating two sets

In this section we prove Theorem 3.1, which is one of the key ingredients of our algorithm. The setting is as follows. We are given a graph GG with fewer than 2k2^k minimal separators and an instance (G′,L′)(G',L') of List 3-Coloring, where G′G' is an induced subgraph of GG. We are also given pairwise disjoint sets A,B,Z⊆V(G)A,B,Z \subseteq V(G), where G[A∪B]G[A \cup B] has at most cc components and Z⊆V(G′)Z \subseteq V(G'). Note that AA and BB do not need to be contained in V(G′)V(G'); this is why, apart from the instance (G′,L′)(G',L'), we need the graph GG. Our aim is to destroy all AA-BB-paths in GG through ZZ by removing vertices of ZZ from the instance, i.e., to obtain subinstances (G′′,L′′)(G'',L'') such that dist⁡G(A,B∣Z∩V(G′′))=∞\operatorname{dist}_G(A,B \mid Z \cap V(G'')) = \infty. We show that this can be done if dist⁡G(A,B∣Z)≥3\operatorname{dist}_G(A,B \mid Z) \geq3, i.e., AA and BB are anticomplete and do not have common neighbors in ZZ.

Theorem 3.1. Let GG be an nn-vertex graph with μ(G)<2k\mu(G) < 2^k, and let (G′,L′)(G',L') be an instance of List 3-Coloring, where G′G' is an induced subgraph of GG. Let A,B,Z⊆V(G)A,B,Z \subseteq V(G) be pairwise disjoint sets such that Z⊆V(G′)Z \subseteq V(G') and G[A∪B]G[A \cup B] has at most cc components. Suppose that dist⁡G(A,B∣Z)≥3\operatorname{dist}_G(A,B \mid Z) \geq3. Then in time nO(1)⋅(4n)6kcn^{O(1)} \cdot(4n)^{6kc} one can compute a family I\mathcal{I} of at most (2n)6kc(2n)^{6kc} subinstances of (G′,L′)(G',L') such that:

  1. I\mathcal{I} is equivalent to (G′,L′)(G',L'), and

  1. for every (G′′,L′′)∈I(G'',L'') \in\mathcal{I}, we have dist⁡G(A,B∣Z∩V(G′′))=∞\operatorname{dist}_G(A,B \mid Z \cap V(G'')) = \infty.

We prove Theorem 3.1 by gradually increasing the distance between AA and BB through the surviving vertices of ZZ, i.e., the value dist⁡G(A,B∣Z∩V(G′′))\operatorname{dist}_G(A,B \mid Z \cap V(G'')) for the constructed subinstances (G′′,L′′)(G'',L''): first from 3 to 4, then to 5, and finally to ∞\infty.

From distance 3 to 4

We start with two purely graph-theoretic lemmas.

Lemma 3.2. Let GG be a graph and let A,B⊆V(G)A,B \subseteq V(G) be disjoint nonempty sets such that G[A∪B]G[A \cup B] has at most cc components. Then every minimal AA-BB-separator in GG is the union of at most c−1c-1 minimal separators in GG.

Proof. Let SS be a minimal AA-BB-separator. We define a sequence S0⊆S1⊆…S_0 \subseteq S_1 \subseteq\ldots of subsets of SS as follows. Let S0=∅S_0 = \varnothing, and for i≥0i \geq0 proceed as follows. If SiS_i is an AA-BB-separator, stop. Otherwise, choose ui∈Au_i \in A and vi∈Bv_i \in B that belong to the same component of G−SiG-S_i. Since SS is an AA-BB-separator, it is also a uiu_i-viv_i-separator, so it contains a minimal uiu_i-viv_i-separator PiP_i, which is a minimal separator in GG. Set Si+1=Si∪PiS_{i+1} = S_i \cup P_i.

For T⊆ST \subseteq S, let q(T)q(T) be the number of components of G−TG-T that intersect A∪BA \cup B. Since T∩(A∪B)=∅T \cap(A \cup B) = \varnothing, each component of G[A∪B]G[A \cup B] is contained in exactly one component of G−TG-T, and each component of G−TG-T that intersects A∪BA \cup B contains a component of G[A∪B]G[A \cup B]. Thus 1≤q(T)≤c1 \leq q(T) \leq c.

Claim 3.2.1. If Si+1S_{i+1} is defined, then q(Si+1)>q(Si)q(S_{i+1}) > q(S_i).

Proof of Claim 3.2.1. As Si⊆Si+1S_i \subseteq S_{i+1}, every component of G−Si+1G-S_{i+1} is contained in a component of G−SiG-S_i. Every component of G−SiG-S_i that intersects A∪BA \cup B contains at least one component of G−Si+1G-S_{i+1} that intersects A∪BA \cup B. Moreover, the component of G−SiG-S_i containing uiu_i and viv_i contains at least two such components, as uiu_i and viv_i are separated by Pi⊆Si+1P_i \subseteq S_{i+1}.

By Claim 3.2.1, the process stops at some SjS_j with j≤c−1j \leq c-1. The set Sj⊆SS_j \subseteq S is an AA-BB-separator and the union of jj minimal separators in GG. By the minimality of SS, we have Sj=SS_j = S. □\square

Let GG be a graph and let A,B⊆V(G)A,B \subseteq V(G) be disjoint sets with dist⁡G(A,B)≥3\operatorname{dist}_G(A,B) \geq3, i.e., N[A]∩N[B]=∅N[A] \cap N[B] = \varnothing. The interface graph of AA and BB in GG is the bipartite graph with vertex set N(A)∪N(B)N(A) \cup N(B) whose edges are all edges of GG between N(A)N(A) and N(B)N(B). Note that the AA-BB-paths of length 3 in GG are exactly the paths axybaxyb such that a∈Aa \in A, b∈Bb \in B, and xyxy is an edge of the interface graph.

Lemma 3.3. Let GG be a graph with μ(G)<2k\mu(G) < 2^k, and let A,B⊆V(G)A, B \subseteq V(G) be disjoint nonempty sets with dist⁡G(A,B)≥3\operatorname{dist}_G(A, B) \ge3, such that G[A∪B]G[A \cup B] has at most cc components. Let HH be the interface graph of AA and BB in GG. Then every minimal vertex cover of HH is the union of at most c−1c-1 minimal separators in G[N[A∪B]]G[N[A \cup B]]. Consequently, HH has at most 2k(c−1)2^{k(c-1)} minimal vertex covers, and they can be enumerated in time ∣V(G)∣O(1)⋅2k(c−1)|V(G)|^{O(1)} \cdot2^{k(c-1)}.

Proof. Replacing GG by G[N[A∪B]]G[N[A \cup B]] changes neither HH nor G[A∪B]G[A \cup B], and does not increase the number of minimal separators. Thus we may assume that V(G)=N[A∪B]V(G) = N[A \cup B]. Let X=N(A)X = N(A) and Y=N(B)Y = N(B). Since N[A]∩N[B]=∅N[A] \cap N[B] = \emptyset, the sets A,B,X,YA, B, X, Y are pairwise disjoint, AA is anticomplete to B∪YB \cup Y, and BB is anticomplete to XX. Thus the only edges of GG between A∪XA \cup X and B∪YB \cup Y are the edges between XX and YY, i.e., the edges of HH.

Claim 3.3.1. The AA-BB-separators in GG are exactly the vertex covers of HH.

Proof of Claim 3.3.1: Both the AA-BB-separators in GG and the vertex covers of HH are subsets of V(G)∖(A∪B)=V(H)V(G) \setminus(A \cup B) = V(H). If CC is a vertex cover of HH, then G−CG - C has no edges between (A∪X)∖C(A \cup X) \setminus C and (B∪Y)∖C(B \cup Y) \setminus C, so CC is an AA-BB-separator in GG. Conversely, if some edge xyxy of HH with x∈Xx \in X and y∈Yy \in Y satisfies x,y∉Cx, y \notin C, then for any neighbor a∈Aa \in A of xx and any neighbor b∈Bb \in B of yy, the path axybaxyb is contained in G−CG - C, so CC is not an AA-BB-separator in GG. ⌟

:::

By Claim 3.3.1, the minimal vertex covers of HH are exactly the minimal AA-BB-separators in GG. By Lemma 3.2, each of them is the union of at most c−1c-1 minimal separators in GG. This proves the first statement. Thus each minimal vertex cover of HH is the union of a sequence of exactly c−1c-1 sets, each of which is ∅\emptyset or a minimal separator in GG. As there are at most μ(G)+1≤2k\mu(G) + 1 \le2^k choices for each set, HH has at most 2k(c−1)2^{k(c-1)} minimal vertex covers. To enumerate them, we list all minimal separators in GG using Theorem 2.1 and check all such unions; this takes time ∣V(G)∣O(1)⋅2k(c−1)|V(G)|^{O(1)} \cdot2^{k(c-1)}, as c≥2c \ge2 because AA and BB are nonempty and anticomplete.

Now we are ready to increase the distance from 3 to 4.

Lemma 3.4. Let GG be an nn-vertex graph with μ(G)<2k\mu(G) < 2^k, and let (G′,L′)(G', L') be an instance of List 3-Coloring, where G′G' is an induced subgraph of GG. Let A,B,Z⊆V(G)A, B, Z \subseteq V(G) be pairwise disjoint sets such that AA and BB are nonempty, Z⊆V(G′)Z \subseteq V(G'), and G[A∪B]G[A \cup B] has at most cc components. Suppose that dist⁡G(A,B∣Z)≥3\operatorname{dist}_G(A, B \mid Z) \ge3. Then in time nO(1)⋅23kcn^{O(1)} \cdot2^{3kc} one can compute a family I\mathcal{I} of at most 23kc2^{3kc} subinstances of (G′,L′)(G', L') such that:

  1. I\mathcal{I} is equivalent to (G′,L′)(G', L'), and

  1. for every (G′′,L′′)∈I(G'', L'') \in\mathcal{I}, we have dist⁡G(A,B∣Z∩V(G′′))≥4\operatorname{dist}_G(A, B \mid Z \cap V(G'')) \ge4.

Proof. Let F=G[A∪B∪Z]F = G[A \cup B \cup Z], and recall that dist⁡F(A,B)=dist⁡G(A,B∣Z)≥3\operatorname{dist}_F(A, B) = \operatorname{dist}_G(A, B \mid Z) \ge3. Let HH be the interface graph of AA and BB in FF. Its vertex set NF(A)∪NF(B)N_F(A) \cup N_F(B) is contained in Z⊆V(G′)Z \subseteq V(G'), and since G′G' is an induced subgraph of GG, every edge of HH is an edge of G′G'. Moreover, μ(F)≤μ(G)<2k\mu(F) \le\mu(G) < 2^k and F[A∪B]=G[A∪B]F[A \cup B] = G[A \cup B] has at most cc components. By Lemma 3.3, the family C\mathcal{C} of all minimal vertex covers of HH has size at most 2k(c−1)2^{k(c-1)} and can be computed in time nO(1)⋅2k(c−1)n^{O(1)} \cdot2^{k(c-1)}.

For every triple C=(C1,C2,C3)∈C3\mathbf{C} = (C_1, C_2, C_3) \in\mathcal{C}^3, we define the list assignment LCL_{\mathbf{C}} of G′G' by LC(v)=L′(v)∖{i∣v∈Ci}L_{\mathbf{C}}(v) = L'(v) \setminus\{i \mid v \in C_i\} for v∈V(G′)v \in V(G'). We exhaustively apply the reduction rules to (G′,LC)(G', L_{\mathbf{C}}); if (R1) is applied, we discard the instance, and otherwise we include the obtained reduced instance in I\mathcal{I}. We have ∣I∣≤∣C∣3≤23k(c−1)≤23kc|\mathcal{I}| \le|\mathcal{C}|^3 \le2^{3k(c-1)} \le2^{3kc}, and the running time is nO(1)⋅23kcn^{O(1)} \cdot2^{3kc}.

Let us show that I\mathcal{I} is equivalent to (G′,L′)(G', L'). As the reduction rules are correct and LC(v)⊆L′(v)L_{\mathbf{C}}(v) \subseteq L'(v) for every v∈V(G′)v \in V(G'), if some instance, then so is (G′,L′)(G', L'). Conversely, let ψ\psi be a proper coloring of (G′,L′)(G', L'). For each i∈[3]i \in[3], the set ψ−1(i)∩V(H)\psi^{-1}(i) \cap V(H) is independent in G′G', and thus in HH, so V(H)∖ψ−1(i)V(H) \setminus\psi^{-1}(i) is a vertex cover of HH; let Ci∈CC_i \in\mathcal{C} be a minimal vertex cover of HH contained in it, and let C=(C1,C2,C3)\mathbf{C} = (C_1, C_2, C_3). For every v∈V(G′)v \in V(G'), we have v∉Cψ(v)v \notin C_{\psi(v)}, so ψ(v)∈LC(v)\psi(v) \in L_{\mathbf{C}}(v). Hence, ψ\psi is a proper coloring of (G′,LC)(G', L_{\mathbf{C}}), so by the correctness of the reduction rules, the instance obtained from C\mathbf{C} is not discarded and is a yes-instance.

Claim 3.4.1. For every (G′′,L′′)∈I(G'', L'') \in\mathcal{I}, no edge of HH has both endpoints in V(G′′)V(G'').

Proof of Claim 3.4.1. Let (G′′,L′′)∈I(G'', L'') \in\mathcal{I} be obtained from CC, and suppose that xyxy is an edge of HH with x,y∈V(G′′)x, y \in V(G''). Since (G′′,L′′)(G'', L'') is reduced, we have ∣L′′(x)∣,∣L′′(y)∣≥2|L''(x)|, |L''(y)| \ge2. On the other hand, L′′(x)⊆LC(x)L''(x) \subseteq L_C(x) and L′′(y)⊆LC(y)L''(y) \subseteq L_C(y), and these sets are disjoint: for every color ii, the vertex cover CiC_i contains xx or yy, so ii is removed from L′(x)L'(x) or from L′(y)L'(y). Two disjoint subsets of [3][3] cannot both have at least two elements, a contradiction.

Finally, consider (G′′,L′′)∈I(G'', L'') \in\mathcal{I}. As Z∩V(G′′)⊆ZZ \cap V(G'') \subseteq Z, we have dist⁡G(A,B∣Z∩V(G′′))≥dist⁡G(A,B∣Z)≥3\operatorname{dist}_G(A, B \mid Z \cap V(G'')) \ge\operatorname{dist}_G(A, B \mid Z) \ge3. Every AA-BB-path in GG through Z∩V(G′′)Z \cap V(G'') is an AA-BB-path in FF, so if it has length 3, then it is of the form axybaxyb, where xyxy is an edge of HH and x,y∈V(G′′)x, y \in V(G''). By Claim 3.4.1, there is no such path, and thus dist⁡G(A,B∣Z∩V(G′′))≥4\operatorname{dist}_G(A, B \mid Z \cap V(G'')) \ge4.

From distance 4 to 5

To increase the distance from 4 to 5, we move all vertices of ZZ adjacent to BB into BB, and apply Lemma 3.4.

Lemma 3.5. Let GG be an nn-vertex graph with μ(G)<2k\mu(G) < 2^k, and let (G′,L′)(G', L') be an instance of List 3-Coloring, where G′G' is an induced subgraph of GG. Let A,B,Z⊆V(G)A, B, Z \subseteq V(G) be pairwise disjoint sets such that AA and BB are nonempty, Z⊆V(G′)Z \subseteq V(G'), and G[A∪B]G[A \cup B] has at most cc components. Suppose that dist⁡G(A,B∣Z)≥4\operatorname{dist}_G(A, B \mid Z) \ge4. Then in time nO(1)⋅23kcn^{O(1)} \cdot2^{3kc} one can compute a family I\mathcal{I} of at most 23kc2^{3kc} subinstances of (G′,L′)(G', L') such that:

  1. I\mathcal{I} is equivalent to (G′,L′)(G', L'), and

  1. for every (G′′,L′′)∈I(G'', L'') \in\mathcal{I}, we have dist⁡G(A,B∣Z∩V(G′′))≥5\operatorname{dist}_G(A, B \mid Z \cap V(G'')) \ge5.

Proof. Let F=G[A∪B∪Z]F = G[A \cup B \cup Z], and recall that dist⁡F(A,B)=dist⁡G(A,B∣Z)≥4\operatorname{dist}_F(A, B) = \operatorname{dist}_G(A, B \mid Z) \ge4. Let B+=NF[B]B^+ = N_F[B] and Z−=Z∖B+Z^- = Z \setminus B^+. As every vertex of B+∖BB^+ \setminus B has a neighbor in BB, every vertex of B+B^+ is at distance at least 3 from AA in FF. In particular, B+⊆B∪ZB^+ \subseteq B \cup Z, so the sets A,B+,Z−A, B^+, Z^- are pairwise disjoint; moreover, B+≠∅B^+ \ne\varnothing and Z−⊆V(G′)Z^- \subseteq V(G'). Every component of G[A∪B+]G[A \cup B^+] intersects A∪BA \cup B, so G[A∪B+]G[A \cup B^+] has at most cc⁡(G[A∪B])≤c\operatorname{cc}(G[A \cup B]) \le c components. Finally, every AA-B+B^+-path in GG through Z−Z^- is a path in FF that ends in B+B^+, so it has length at least 3, i.e., dist⁡G(A,B+∣Z−)≥3\operatorname{dist}_G(A, B^+ \mid Z^-) \ge3.

Thus we can apply Lemma 3.4 to (G′,L′)(G', L') and A,B+,Z−A, B^+, Z^-. In time nO(1)⋅23kcn^{O(1)} \cdot2^{3kc} we obtain a family I\mathcal{I} of at most 23kc2^{3kc} subinstances of (G′,L′)(G', L'), which is equivalent to (G′,L′)(G', L'), and such that dist⁡G(A,B+∣Z−∩V(G′′))≥4\operatorname{dist}_G(A, B^+ \mid Z^- \cap V(G'')) \ge4 for every (G′′,L′′)∈I(G'', L'') \in\mathcal{I}.

Consider (G′′,L′′)∈I(G'', L'') \in\mathcal{I}. As Z∩V(G′′)⊆ZZ \cap V(G'') \subseteq Z, we have dist⁡G(A,B∣Z∩V(G′′))≥dist⁡G(A,B∣Z)≥4\operatorname{dist}_G(A, B \mid Z \cap V(G'')) \ge\operatorname{dist}_G(A, B \mid Z) \ge4. Suppose that there is an AA-BB-path in GG through Z∩V(G′′)Z \cap V(G'') of length exactly 4, say az1z2z3baz_1z_2z_3b, where a∈Aa \in A, z1,z2,z3∈Z∩V(G′′)z_1, z_2, z_3 \in Z \cap V(G''), and b∈Bb \in B. Then z3∈B+z_3 \in B^+, and z1,z2∉B+z_1, z_2 \notin B^+, as they are at distance at most 2 from AA in FF. Thus az1z2z3az_1z_2z_3 is an AA-B+B^+-path in GG through Z−∩V(G′′)Z^- \cap V(G'') of length 3, a contradiction.

Combining Lemmas 3.4 and 3.5, we obtain the following.

Corollary 3.6. Let GG be an nn-vertex graph with μ(G)<2k\mu(G) < 2^k, and let (G′,L′)(G', L') be an instance of List 3-Coloring, where G′G' is an induced subgraph of GG. Let A,B,Z⊆V(G)A, B, Z \subseteq V(G) be pairwise disjoint sets such that AA and BB are nonempty, Z⊆V(G′)Z \subseteq V(G'), and G[A∪B]G[A \cup B] has at most cc components. Suppose that dist⁡G(A,B∣Z)≥3\operatorname{dist}_G(A, B \mid Z) \ge3. Then in time nO(1)⋅26kcn^{O(1)} \cdot2^{6kc} one can compute a family I\mathcal{I} of at most 26kc2^{6kc} subinstances of (G′,L′)(G', L') such that:

  1. I\mathcal{I} is equivalent to (G′,L′)(G', L'), and

  1. for every (G′′,L′′)∈I(G'', L'') \in\mathcal{I}, we have dist⁡G(A,B∣Z∩V(G′′))≥5\operatorname{dist}_G(A, B \mid Z \cap V(G'')) \ge5.

Proof. We apply Lemma 3.4 to (G′,L′)(G', L') and A,B,ZA, B, Z. For every obtained instance (G1,L1)(G_1, L_1), we have dist⁡G(A,B∣Z∩V(G1))≥4\operatorname{dist}_G(A, B \mid Z \cap V(G_1)) \ge4, so we can apply Lemma 3.5 to (G1,L1)(G_1, L_1) and A,B,Z∩V(G1)A, B, Z \cap V(G_1). Let I\mathcal{I} be the family of all instances obtained in this way. By the transitivity of equivalence, I\mathcal{I} is a family of at most 23kc⋅23kc2^{3kc} \cdot2^{3kc} subinstances of (G′,L′)(G', L') that is equivalent to (G′,L′)(G', L'), and it is computed in time nO(1)⋅23kc⋅23kcn^{O(1)} \cdot2^{3kc} \cdot2^{3kc}. Moreover, if (G′′,L′′)∈I(G'', L'') \in\mathcal{I} is obtained from (G1,L1)(G_1, L_1), then Z∩V(G′′)=(Z∩V(G1))∩V(G′′)Z \cap V(G'') = (Z \cap V(G_1)) \cap V(G''), and thus dist⁡G(A,B∣Z∩V(G′′))≥5\operatorname{dist}_G(A, B \mid Z \cap V(G'')) \ge5.

From distance 5 to infinity

The crucial property of distance 5 is that no vertex is at distance at most 2 from both AA and BB. The following lemma uses this to reduce the problem to one where the distance is again at least 3, but the set ZZ is at most half as large.

Lemma 3.7. Let GG be a graph and let A,B,Z⊆V(G)A, B, Z \subseteq V(G) be pairwise disjoint sets such that dist⁡G(A,B∣Z)≥5\operatorname{dist}_{G}(A, B \mid Z) \ge5. Then in polynomial time one can compute sets A′,B′,Z′⊆V(G)A', B', Z' \subseteq V(G) such that:

  1. A′,B′,Z′A', B', Z' are pairwise disjoint, A⊆A′A \subseteq A', B⊆B′B \subseteq B', Z′⊆ZZ' \subseteq Z, and ∣Z′∣≤∣Z∣/2\lvert Z' \rvert\le\lvert Z\rvert/2,

  1. cc⁡(G[A′∪B′])≤cc⁡(G[A∪B])\operatorname{cc}(G[A' \cup B']) \le\operatorname{cc}(G[A \cup B]),

  1. dist⁡G(A′,B′∣Z′)≥3\operatorname{dist}_{G}(A', B' \mid Z') \ge3, and

  1. every AA-BB-path in GG through ZZ contains a subpath that is an A′A'-B′B'-path in GG through Z′Z'.

Proof. Let F=G[A∪B∪Z]F = G[A \cup B \cup Z], and recall that dist⁡F(A,B)=dist⁡G(A,B∣Z)≥5\operatorname{dist}_{F}(A, B) = \operatorname{dist}_{G}(A, B \mid Z) \ge5. Let Q=NF[NF[B]]Q = N_{F}[N_{F}[B]] be the set of vertices at distance at most 2 from BB in FF. Every vertex of QQ is at distance at least 3 from AA in FF; in particular, A∩Q=∅A \cap Q = \varnothing. Let CC be the union of the vertex sets of all components of F−QF - Q that intersect AA; intuitively, CC consists of the vertices that can be reached from AA without coming close to BB. Then A⊆CA \subseteq C, and every vertex of CC is at distance at least 3 from BB in FF, as C∩Q=∅C \cap Q = \varnothing. As B⊆QB \subseteq Q, we have C⊆A∪ZC \subseteq A \cup Z, so ZZ is the disjoint union of C∖AC \setminus A and Z∖CZ \setminus C. If ∣C∖A∣≤∣Z∣/2\lvert C \setminus A\rvert\le\lvert Z\rvert/2, we set (A′,B′,Z′)=(A,Q,C∖A)(A', B', Z') = (A, Q, C \setminus A), and otherwise we set (A′,B′,Z′)=(C,B,Z∖C)(A', B', Z') = (C, B, Z \setminus C). In both cases, ∣Z′∣≤∣Z∣/2\lvert Z'\rvert\le\lvert Z\rvert/2, and clearly these sets can be computed in polynomial time.

We first verify conditions 2 and 3, simultaneously for both cases. Every vertex of QQ is joined to BB by a path all of whose vertices belong to QQ, and every vertex of CC is joined to AA by a path all of whose vertices belong to CC. Hence every component of G[A′∪B′]G[A' \cup B'] intersects A∪B⊆A′∪B′A \cup B \subseteq A' \cup B', and thus cc⁡(G[A′∪B′])≤cc⁡(G[A∪B])\operatorname{cc}(G[A' \cup B']) \le\operatorname{cc}(G[A \cup B]). Moreover, A′∪B′∪Z′⊆V(F)A' \cup B' \cup Z' \subseteq V(F), so every A′A'-B′B'-path through Z′Z' is a path in FF that joins a vertex of A′A' with a vertex of B′B'. In the first case, its endpoint in B′=QB' = Q is at distance at least 3 from A′=AA' = A in FF, and in the second case, its endpoint in A′=CA' = C is at distance at least 3 from B′=BB' = B in FF. Thus dist⁡G(A′,B′∣Z′)≥3\operatorname{dist}_{G}(A', B' \mid Z') \ge3.

Now suppose that (A′,B′,Z′)=(A,Q,C∖A)(A', B', Z') = (A, Q, C \setminus A). Condition 1 holds as A∩Q=∅A \cap Q = \varnothing, C∩Q=∅C \cap Q = \varnothing, B⊆QB \subseteq Q, and C∖A⊆ZC \setminus A \subseteq Z. For condition 4, let v0v1…vmv_0v_1 \ldots v_m be an AA-BB-path through ZZ, where v0∈Av_0 \in A and vm∈Bv_m \in B. As v0∉Qv_0 \notin Q and vm∈Qv_m \in Q, there is a minimum index i≥1i \ge1 such that vi∈Qv_i \in Q. Then v0v1…vi−1v_0v_1 \ldots v_{i-1} is a path in F−QF - Q that contains v0∈Av_0 \in A, so v0,…,vi−1∈Cv_0, \ldots, v_{i-1} \in C. As v1,…,vi−1∈Zv_1, \ldots, v_{i-1} \in Z, they belong to C∖AC \setminus A, and thus v0v1…viv_0v_1 \ldots v_i is an AA-QQ-path through C∖AC \setminus A.

Finally, suppose that (A′,B′,Z′)=(C,B,Z∖C)(A', B', Z') = (C, B, Z \setminus C). Condition 1 holds as A⊆CA \subseteq C and C∩B⊆C∩Q=∅C \cap B \subseteq C \cap Q = \varnothing. For condition 4, let v0v1…vmv_0v_1 \ldots v_m be an AA-BB-path through ZZ, where v0∈Av_0 \in A and vm∈Bv_m \in B. As v0∈Cv_0 \in C and vm∉Cv_m \notin C, there is a maximum index i≤m−1i \le m-1 such that vi∈Cv_i \in C. Then vi+1,…,vm−1∈Z∖Cv_{i+1}, \ldots, v_{m-1} \in Z \setminus C, and thus vivi+1…vmv_iv_{i+1} \ldots v_m is a CC-BB-path through Z∖CZ \setminus C.

Now we are ready to prove Theorem 3.1. We use Corollary 3.6 to increase the distance between AA and BB to 5, and then Lemma 3.7 to reduce the problem to one where ZZ is at most half as large, which we solve recursively. As ZZ is halved in each step, the recursion terminates after O(log⁡n)O(\log n) steps.

Proof of Theorem 3.1. We describe a recursive algorithm, and prove its correctness by induction on ∣Z∣\lvert Z\rvert. If dist⁡G(A,B∣Z)=∞\operatorname{dist}_{G}(A, B \mid Z) = \infty, then the algorithm returns I={(G,L′)}\mathcal{I} = \{(G, L')\}, which clearly satisfies conditions 1 and 2. Otherwise, AA and BB are nonempty, and Z≠∅Z \ne\varnothing, as AA and BB are anticomplete. By Corollary 3.6, in time nO(1)⋅26kcn^{O(1)} \cdot2^{6kc} we compute a family J\mathcal{J} of at most 26kc2^{6kc} subinstances of (G′,L′)(G', L'), which is equivalent to (G′,L′)(G', L'), such that dist⁡G(A,B∣Z∩V(G2))≥5\operatorname{dist}_{G}(A, B \mid Z \cap V(G_2)) \ge5 for every (G2,L2)∈J(G_2, L_2) \in\mathcal{J}.

Consider (G2,L2)∈J(G_2, L_2) \in\mathcal{J}. We apply Lemma 3.7 to A,B,Z∩V(G2)A, B, Z \cap V(G_2), and obtain sets A′,B′,Z′A', B', Z'. By Lemma 3.7, these sets are pairwise disjoint, Z′⊆V(G2)Z' \subseteq V(G_2), G[A′∪B′]G[A' \cup B'] has at most cc⁡(G[A∪B])≤c\operatorname{cc}(G[A \cup B]) \le c components, dist⁡G(A′,B′∣Z′)≥3\operatorname{dist}_{G}(A', B' \mid Z') \ge3, and ∣Z′∣≤∣Z∣/2<∣Z∣\lvert Z'\rvert\le\lvert Z\rvert/2 < \lvert Z\rvert. As G2G_2 is an induced subgraph of GG, we can call the algorithm recursively for (G2,L2)(G_2, L_2) and A′,B′,Z′A', B', Z'. By the induction hypothesis, it returns a family I(G2,L2)\mathcal{I}_{(G_2,L_2)} of subinstances of (G2,L2)(G_2, L_2), which is equivalent to (G2,L2)(G_2, L_2), such that dist⁡G(A′,B′∣Z′∩V(G′′))=∞\operatorname{dist}_{G}(A', B' \mid Z' \cap V(G'')) = \infty for every (G′′,L′′)∈I(G2,L2)(G'', L'') \in\mathcal{I}_{(G_2,L_2)}. The algorithm returns I=⋃(G2,L2)∈JI(G2,L2)\mathcal{I} = \bigcup_{(G_2,L_2) \in\mathcal{J}} \mathcal{I}_{(G_2,L_2)}.

By the transitivity of equivalence, I\mathcal{I} is a family of subinstances of (G′,L′)(G',L') that is equivalent to (G′,L′)(G',L'). Now consider (G′′,L′′)∈I(G2,L2)(G'',L'') \in\mathcal{I}_{(G_2,L_2)} for some (G2,L2)∈J(G_2,L_2) \in\mathcal{J}, and suppose that there is an AA-BB-path in GG through Z∩V(G′′)Z \cap V(G''). As V(G′′)⊆V(G2)V(G'') \subseteq V(G_2), this path is an AA-BB-path through Z∩V(G2)Z \cap V(G_2). By Lemma 3.7, it contains a subpath that is an A′A'-B′B'-path through Z′Z'. The internal vertices of this subpath are internal vertices of the original path, so they belong to Z′∩V(G′′)Z' \cap V(G''). Thus the subpath is an A′A'-B′B'-path in GG through Z′∩V(G′′)Z' \cap V(G''), a contradiction.

Size and running time. Every call makes at most 26kc2^{6kc} recursive calls, in each of which ZZ is at most half as large, and only calls with Z≠∅Z \ne\varnothing make recursive calls. As ∣Z∣≤n|Z| \le n, the recursion tree has depth at most log⁡n+1\log n + 1, so it has at most 26kc(log⁡n+1)=(2n)6kc2^{6kc(\log n+1)} = (2n)^{6kc} leaves and at most 2⋅(2n)6kc2 \cdot(2n)^{6kc} nodes. Every instance in I\mathcal{I} originates from a leaf, and each leaf returns at most one instance, so ∣I∣≤(2n)6kc|\mathcal{I}| \le(2n)^{6kc}. Apart from the recursive calls, each call takes time nO(1)⋅26kcn^{O(1)} \cdot2^{6kc} by Corollary 3.6 and Lemma 3.7. Thus the total running time is nO(1)⋅26kc⋅(2n)6kc=nO(1)⋅(4n)6kcn^{O(1)} \cdot2^{6kc} \cdot(2n)^{6kc} = n^{O(1)} \cdot(4n)^{6kc}.

Proof of the main theorem

In this section we prove the main result of the paper.

Theorem 4.1. Every instance (G,L)(G,L) of List 3-Coloring, where GG has n≥2n \ge2 vertices and μ(G)<2k\mu(G) < 2^k for an integer k≥1k \ge1, can be solved in time nO(k2log⁡3n)n^{O(k^2 \log^3 n)}.

Observe that Theorem 4.1 implies Theorem 1.3. Indeed, if G\mathcal{G} is a tame (resp., quasitame) class of graphs, then every nn-vertex graph G∈GG \in\mathcal{G} with n≥2n \ge2 satisfies μ(G)<2k\mu(G) < 2^k for some k=O(log⁡n)k = O(\log n) (resp., k=O(log⁡an)k = O(\log^a n), where aa is the constant from the definition of quasitame classes), so by Theorem 4.1, List 3-Coloring can be solved on G\mathcal{G} in time nO(log⁡5n)n^{O(\log^5 n)} (resp., nO(log⁡2a+3n)n^{O(\log^{2a+3} n)}), which is quasipolynomial.

The main technical step is the following lemma, which encapsulates the branching scheme.

Lemma 4.2. Let (G,L)(G,L) be an instance of List 3-Coloring, where GG has n≥2n \ge2 vertices and μ(G)<2k\mu(G) < 2^k for an integer k≥1k \ge1. Then in time nO(k2log⁡2n)n^{O(k^2 \log^2 n)} one can compute a family I\mathcal{I} of subinstances of (G,L)(G,L) such that:

  1. I\mathcal{I} is equivalent to (G,L)(G,L), and

  1. for every (G′,L′)∈I(G',L') \in\mathcal{I}, every component of G′G' has at most n/2n/2 vertices.

Let us first show how Lemma 4.2 implies Theorem 4.1.

Proof of Theorem 4.1 assuming Lemma 4.2. We apply Lemma 4.2 to (G,L)(G,L), and for every obtained instance, we recursively solve its restrictions to all components of its graph; instances with one vertex are solved directly. Correctness follows from Lemma 4.2. The graphs of all instances in the recursion are induced subgraphs of GG, so they have fewer than 2k2^k minimal separators, and the number of vertices halves in each recursive call. Thus the recursion has depth O(log⁡n)O(\log n), and each call takes time nO(k2log⁡2n)n^{O(k^2 \log^2 n)} and makes at most nO(k2log⁡2n)n^{O(k^2 \log^2 n)} recursive calls, which gives the running time nO(k2log⁡3n)n^{O(k^2 \log^3 n)}. □\square

The rest of this section is devoted to the proof of Lemma 4.2. We will repeatedly use the following operation. Let (G′,L′)(G',L') be an instance of List 3-Coloring, and let X⊆V(G′)X \subseteq V(G') be nonempty. Guessing the coloring of XX works as follows. For every function φ\varphi that assigns to each x∈Xx \in X a color φ(x)∈L′(x)\varphi(x) \in L'(x), we restrict the list of every x∈Xx \in X to {φ(x)}\{\varphi(x)\}, and exhaustively apply the reduction rules. We discard every instance to which (R1) is applied, and return the family of all remaining reduced instances. This family consists of at most 3∣X∣3^{|X|} subinstances of (G′,L′)(G',L'), and it is equivalent to (G′,L′)(G',L'), as we consider all colorings of XX and the reduction rules are correct. For a single vertex vv, we write guessing the color of vv instead of guessing the coloring of {v}\{v\}.

Proof of Lemma 4.2. Let us start with an overview. We repeatedly find a set DD of at most 2k2k vertices whose closed neighborhood is a balanced separator, and guess the coloring of DD; we call DD a center. Afterwards, every remaining neighbor of DD has only two colors in its list. Once we have O(log⁡n)O(\log n) pairwise anticomplete centers such that no vertex is adjacent to all of them, their neighborhoods are balanced separators with empty intersection. We make them pairwise non-crossing using Theorem 3.1, and conclude using Theorem 2.3. To ensure that no vertex is adjacent to too many centers, we guess the colors of vertices whose closed neighborhoods contain many vertices adjacent to centers. In all branches but one, many of them are deleted, which is captured by a potential function.

The procedure. First, we exhaustively apply the reduction rules to (G,L)(G,L); if (R1) is applied, we output the empty family, which is equivalent to (G,L)(G,L). Thus we may assume that (G,L)(G,L) is reduced. Let hh be the smallest integer such that 2h>n2^h > n; note that h=O(log⁡n)h = O(\log n).

The procedure maintains a reduced subinstance (G′,L′)(G',L') of (G,L)(G,L), initially equal to (G,L)(G,L), and a sequence D1,…,DtD_1,\ldots,D_t of centers, initially empty, which are pairwise disjoint subsets of V(G)∖V(G′)V(G) \setminus V(G'). For v∈V(G′)v \in V(G'), let m(v)m(v) be the number of centers that contain a neighbor of vv, and let w(v)=2m(v)−1w(v) = 2^{m(v)} - 1. For X⊆V(G′)X \subseteq V(G'), let w(X)=∑v∈Xw(v)w(X) = \sum_{v \in X} w(v); we call w(V(G′))w(V(G')) the potential of (G′,L′)(G',L'). A vertex v∈V(G′)v \in V(G') is heavy if w(NG′[v])≥nw(N_{G'}[v]) \ge n. The greedy selection repeatedly selects the remaining center with the largest index, and removes it together with all remaining centers that are not anticomplete to it, until no center remains; clearly, the selected centers are pairwise anticomplete. In each instance, the procedure applies the first applicable step among the following ones.

(S1) If every component of G′G' has at most n/2n/2 vertices, output (G′,L′)(G',L').

(S2) If some vertex v∈V(G′)v \in V(G') is heavy, guess the color of vv, and continue with each obtained instance.

(S3) If the greedy selection selects fewer than hh centers, find a smallest set D⊆V(G′)D \subseteq V(G') such that NG′[D]N_{G'}[D] is a 1/21/2-balanced separator in G′G', by checking all sets in the order of increasing size. Note that D≠∅D \ne\varnothing, as (S1) does not apply. Guess the coloring of DD, and continue with each obtained instance, with Dt+1=DD_{t+1} = D as a new center.

(S4) Otherwise, apply the finishing step described below to (G′,L′)(G',L') and the first hh centers selected by the greedy selection, and output the obtained family.

Note that the procedure does not use kk, and neither does the algorithm of Theorem 3.1, which we apply in the finishing step.

Analysis of steps (S1)–(S3). As μ(G′)≤μ(G)<2k\mu(G') \le\mu(G) < 2^k, by Lemma 2.2, every center has at most 2k2k vertices. Let M=2kh2M = 2kh^2.

Claim 4.2.1. Every vertex v∈V(G′)v \in V(G') with m(v)≥1m(v) \ge1 satisfies ∣L′(v)∣=2\lvert L'(v)\rvert= 2.

Proof of Claim 4.2.1: Let xx be a neighbor of vv in some center. When we guessed the coloring of this center, the vertex xx was deleted by (R2), and thus its color was removed from the list of vv. As lists never grow, we have ∣L′(v)∣≤2\lvert L'(v)\rvert\le2, and ∣L′(v)∣≥2\lvert L'(v)\rvert\ge2, as (G′,L′)(G',L') is reduced.

Claim 4.2.2. Let v∈V(G′)v \in V(G') be heavy. For every color i∈L′(v)i \in L'(v) except at most one, the instance obtained for ii when guessing the color of vv, if not discarded, has potential at most w(V(G′))−n/2w(V(G')) - n/2.

Proof of Claim 4.2.2: For i∈[3]i \in[3], let Xi={u∈NG′[v]∣i∈L′(u)}X_i = \{u \in N_{G'}[v] \mid i \in L'(u)\}. By Claim 4.2.1, every vertex uu with w(u)>0w(u) > 0 has exactly two colors in its list, so w(X1)+w(X2)+w(X3)=2w(NG′[v])w(X_1) + w(X_2) + w(X_3) = 2w(N_{G'}[v]). As w(Xi)≤w(NG′[v])w(X_i) \le w(N_{G'}[v]) for every ii, at most one color ii satisfies w(Xi)<w(NG′[v])/2w(X_i) < w(N_{G'}[v])/2. Consider any other color i∈L′(v)i \in L'(v), so that w(Xi)≥w(NG′[v])/2≥n/2w(X_i) \ge w(N_{G'}[v])/2 \ge n/2, and suppose that the instance (G′′,L′′)(G'',L'') obtained for ii is not discarded. Every vertex u∈Xiu \in X_i with w(u)>0w(u) > 0 is deleted in (G′′,L′′)(G'',L''): either u=vu = v, or uu is a neighbor of vv, so it loses the color ii and is left with at most one color, while (G′′,L′′)(G'',L'') is reduced. As the weights of the remaining vertices do not change, the potential decreases by at least w(Xi)≥n/2w(X_i) \ge n/2.

Claim 4.2.3. If no vertex of G′G' is heavy, then m(v)<hm(v) < h for every v∈V(G′)v \in V(G').

Proof of Claim 4.2.3: We have 2m(v)−1=w(v)≤w(NG′[v])<n2^{m(v)} - 1 = w(v) \le w(N_{G'}[v]) < n, so 2m(v)≤n<2h2^{m(v)} \le n < 2^h.

Claim 4.2.4. If t≥Mt \ge M, then the greedy selection selects at least hh centers. Consequently, we always have t≤Mt \le M.

Proof of Claim 4.2.4. Consider s∈[t]s \in[t]. When DsD_s was found in (S3), it was contained in the vertex set of the current instance, and no vertex of this instance was heavy. Thus, by Claim 4.2.3, every vertex of DsD_s has a neighbor in fewer than hh of the centers D1,…,Ds−1D_1,\ldots,D_{s-1}, so DsD_s is anticomplete to all but at most 2k(h−1)2k(h-1) of them. Hence, each round of the greedy selection removes at most 2k(h−1)+1≤2kh2k(h-1)+1 \le2kh centers, so there are at least t/(2kh)t/(2kh) rounds, which is at least hh if t≥Mt \ge M. In particular, (S3) is not applied if t≥Mt \ge M, so we always have t≤Mt \le M.

Claim 4.2.5. Every execution of (S3) increases the potential by less than (2k+1)n(2k+1)n.

Proof of Claim 4.2.5. Let DD be the center found in (S3) for (G′,L′)(G',L'), and let (G′′,L′′)(G'',L'') be an obtained instance. Compared to (G′,L′)(G',L'), some vertices are deleted, and for every v∈V(G′′)v \in V(G'') that has a neighbor in DD, the weight w(v)\mathrm{w}(v) changes to 2w(v)+12\mathrm{w}(v)+1; all such vertices vv belong to NG′[D]N_{G'}[D]. As no vertex of G′G' is heavy, the potential increases by at most

∑v∈NG′[D](w(v)+1)≤∣V(G′)∣+∑x∈Dw(NG′[x])<n+2kn.\sum_{v\in N_{G'}[D]}(\mathrm{w}(v)+1)\leq|V(G')|+\sum_{x\in D}\mathrm{w}(N_{G'}[x])<n+2kn.

Claim 4.2.6. Steps (S1)–(S3) produce at most nO(k2h2)n^{O(k^2h^2)} instances, in total time nO(k2h2)n^{O(k^2h^2)}.

Proof of Claim 4.2.6. Consider the search tree whose nodes are the instances produced by the procedure, where the children of an instance are the instances obtained from it by guessing in (S2) or (S3). Every guess deletes at least one vertex, so every root-to-leaf path has at most nn edges. For each guess of the color of a vertex vv in (S2), we call the edge to the child obtained for the exceptional color from Claim 4.2.2 default (if there is one); all other edges of the tree are marked.

Consider a root-to-leaf path. By Claim 4.2.4, it contains at most MM edges corresponding to (S3), each leading to one of at most 32k3^{2k} children. By Claim 4.2.2, each marked edge corresponding to (S2) decreases the potential by at least n/2n/2. The potential is initially 00 and never negative, and by Claim 4.2.5, it increases only in (S3), by less than (2k+1)n(2k+1)n each time. Hence, the path contains fewer than 2(2k+1)M2(2k+1)M marked edges corresponding to (S2), each leading to one of at most 33 children. A root-to-leaf path is determined by its length, the positions of its marked edges, and the children chosen at its marked edges. Thus there are at most (n+1)(4k+3)M+1⋅32kM⋅3(4k+2)M=nO(kM)=nO(k2h2)(n+1)^{(4k+3)M+1}\cdot3^{2kM}\cdot3^{(4k+2)M}=n^{O(kM)}=n^{O(k^2h^2)} root-to-leaf paths, and the tree has at most n+1n+1 times as many nodes. Each node is processed in time n2k+O(1)n^{2k+O(1)}, as every center has at most 2k2k vertices, which proves the claim.

The finishing step. Consider an instance (G′,L′)(G',L') to which (S4) is applied, and let C1,…,ChC_1,\ldots,C_h be the first hh centers selected by the greedy selection; recall that they are pairwise anticomplete.

Claim 4.2.7. Let G′′G'' be an induced subgraph of G′G'. For every j∈[h]j \in[h], every component of G′′−NG(Cj)G''-N_G(C_j) has at most n/2n/2 vertices. Moreover, no vertex of G′′G'' belongs to all the sets NG(Cj)N_G(C_j).

Proof of Claim 4.2.7. Fix jj, and let HH be the graph of the instance in which CjC_j was found in (S3). Then NH[Cj]N_H[C_j] is a 1/21/2-balanced separator in HH, and V(G′′)⊆V(G′)⊆V(H)∖CjV(G'')\subseteq V(G')\subseteq V(H)\setminus C_j. Thus G′′−NG(Cj)G''-N_G(C_j) is an induced subgraph of H−NH[Cj]H-N_H[C_j], so each of its components has at most ∣V(H)∣/2≤n/2|V(H)|/2\leq n/2 vertices. Finally, a vertex in all the sets NG(Cj)N_G(C_j) would contradict Claim 4.2.3, as no vertex of G′G' is heavy.

Now we make these separators pairwise non-crossing. We start with the family {(G′,L′)}\{(G',L')\}, and consider the pairs (j,j′)(j,j') with 1≤j<j′≤h1\leq j<j'\leq h one by one. For the pair (j,j′)(j,j'), we replace each instance (G1,L1)(G_1,L_1) of the current family by the family obtained by applying Theorem 3.1 to GG, (G1,L1)(G_1,L_1), A=CjA=C_j, B=Cj′B=C_{j'}, Z=V(G1)∖(NG(Cj)∩NG(Cj′))Z=V(G_1)\setminus(N_G(C_j)\cap N_G(C_{j'})), and c=4kc=4k. The assumptions of Theorem 3.1 are satisfied: the sets CjC_j, Cj′C_{j'}, and ZZ are pairwise disjoint, as the centers are disjoint and consist of deleted vertices; the graph G[Cj∪Cj′]G[C_j\cup C_{j'}] has at most ∣Cj∣+∣Cj′∣≤4k|C_j|+|C_{j'}|\leq4k components; and dist⁡G(Cj,Cj′∣Z)≥3\operatorname{dist}_G(C_j,C_{j'}\mid Z)\geq3, as CjC_j and Cj′C_{j'} are anticomplete and no vertex of ZZ has neighbors in both of them. Let T′\mathcal{T}' be the family obtained after considering all pairs. By the transitivity of equivalence, T′\mathcal{T}' is equivalent to (G′,L′)(G',L'), and by Theorem 3.1, T′\mathcal{T}' consists of at most (2n)24k2h2(2n)^{24k^2h^2} instances and is computed in time nO(k2h2)n^{O(k^2h^2)}.

Claim 4.2.8. Let (G′′,L′′)∈T′(G'',L'')\in\mathcal{T}', and let Sj=NG(Cj)∩V(G′′)S_j=N_G(C_j)\cap V(G'') for j∈[h]j\in[h]. Then the sets S1,…,ShS_1,\ldots,S_h are pairwise non-crossing in G′′G''. Proof of Claim 4.2.8: Suppose that for some j<j′j<j', there is a path PP in G′′−(Sj∩Sj′)G''-(S_j\cap S_{j'}) from a vertex x∈Sj∖Sj′x\in S_j\setminus S_{j'} to a vertex y∈Sj′∖Sjy\in S_{j'}\setminus S_j. When considering the pair (j,j′)(j,j'), we applied Theorem 3.1 to some instance (G1,L1)(G_1,L_1), and obtained an instance (G2,L2)(G_2,L_2) with V(G′′)⊆V(G2)⊆V(G1)V(G'')\subseteq V(G_2)\subseteq V(G_1) and dist⁡G(Cj,Cj′∣Z∩V(G2))=∞\operatorname{dist}_G(C_j,C_{j'}\mid Z\cap V(G_2))=\infty, where Z=V(G1)∖(NG(Cj)∩NG(Cj′))Z=V(G_1)\setminus(N_G(C_j)\cap N_G(C_{j'})). The vertices of PP belong to V(G′′)V(G'') but not to NG(Cj)∩NG(Cj′)N_G(C_j)\cap N_G(C_{j'}), so they belong to Z∩V(G2)Z\cap V(G_2). Thus extending PP by a neighbor of xx in CjC_j and a neighbor of yy in Cj′C_{j'} yields a CjC_j-Cj′C_{j'}-path in GG through Z∩V(G2)Z\cap V(G_2), a contradiction. ⌟

Let (G′′,L′′)∈I′(G'',L'')\in\mathcal{I}'; we show that every component of G′′G'' has at most n/2n/2 vertices. This is clear if ∣V(G′′)∣≤n/2|V(G'')|\le n/2, so assume otherwise, and let δ=n/(2∣V(G′′)∣)<1\delta=n/(2|V(G'')|)<1. By Claims 4.2.7 and 4.2.8, the sets S1,…,ShS_1,\ldots,S_h are pairwise non-crossing δ\delta-balanced separators in G′′G'', and no vertex of G′′G'' belongs to all of them. Hence, by Theorem 2.3, every component of G′′G'' has at most δ∣V(G′′)∣=n/2\delta|V(G'')|=n/2 vertices. The finishing step outputs I′\mathcal{I}'.

Conclusion. Every step replaces an instance by an equivalent family of subinstances, so by the transitivity of equivalence, the output family I\mathcal{I} is equivalent to (G,L)(G,L). The instances output in (S1) and in the finishing step satisfy condition 2. By Claim 4.2.6, steps (S1)–(S3) produce nO(k2h2)n^{O(k^2h^2)} instances in time nO(k2h2)n^{O(k^2h^2)}, and for each of them, the finishing step takes time nO(k2h2)n^{O(k^2h^2)}. As h=O(log⁡n)h=O(\log n), the total running time is nO(k2log⁡2n)n^{O(k^2\log^2 n)}.

Conclusion

We showed that List 3-Coloring can be solved in quasipolynomial time on every (quasi)tame class of graphs. This does not resolve the main question: whether for tame classes the running time can be improved to polynomial.

Question 1.2. Can List 3-Coloring be solved in polynomial time on every tame class of graphs?

A particularly interesting special case is that of circle graphs, which form a tame class; see the introduction for the status of the problem in this class.

Recall that MWIS and its generalizations, such as the (tw⁡≤r,ψ)(\operatorname{tw}\le r,\psi)-MWIS problem, are solved in tame classes using the framework of potential maximal cliques [7, 14]. It is unclear whether potential maximal cliques can be useful for List 3-Coloring; in particular, all known algorithms for List 3-Coloring in tame classes, as well as in PtP_t-free graphs, follow a different route. This leads to the following meta-question.

Question 5.1. Is there a natural problem that generalizes both (tw⁡≤r,ψ)(\operatorname{tw}\le r,\psi)-MWIS and List 3-Coloring, and can be solved in (quasi)polynomial time on every tame class of graphs?

Acknowledgement

The arguments leading to the proof were found with the help of ChatGPT. The presentation and exposition are due to the author. Claude was used to polish the write-up. The author takes full responsibility for the content of the paper.

References

  1. [1]T. Abrishami, M. Chudnovsky, C. Dibek, S. Thomassé, N. Trotignon, and K. Vušković. Graphs with polynomially many minimal separators. Journal of Combinatorial Theory, Series B, 152:248–280, 2022.DOI
  2. [2]T. Abrishami, M. Chudnovsky, M. Pilipczuk, P. Rzążewski, and P. Seymour. Induced subgraphs of bounded treewidth and the container method. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, pages 1948–1964. SIAM, 2021.
  3. [3]Ajaykrishnan E S, R. Ganian, D. Lokshtanov, and V. Surianarayanan. A quasi-polynomial time algorithm for 3-coloring circle graphs. In 2026 SIAM Symposium on Simplicity in Algorithms, SOSA 2026, pages 65–80. SIAM, 2026.arxiv.org/abs/2511.09707
  4. [4]P. Bachmann, I. Rutter, and P. Stumpf. On 3-coloring circle graphs. Journal of Graph Algorithms and Applications, 28(1):389–402, 2024.arxiv.org/abs/2309.02258
  5. [5]A. Berry, J. Bordat, and O. Cogis. Generating all the minimal separators of a graph. International Journal of Foundations of Computer Science, 11(3):397–403, 2000.
  6. [6]F. Bonomo, M. Chudnovsky, P. Maceli, O. Schaudt, M. Stein, and M. Zhong. Three-coloring and list three-coloring of graphs without induced paths on seven vertices. Combinatorica, 38(4):779–801, 2018.DOI
  7. [7]V. Bouchitté and I. Todinca. Treewidth and minimum fill-in: Grouping the minimal separators. SIAM Journal on Computing, 31(1):212–232, 2001.DOI
  8. [8]V. Bouchitté and I. Todinca. Listing all potential maximal cliques of a graph. Theoretical Computer Science, 276(1-2):17–32, 2002.
  9. [9]H. Broersma, F. V. Fomin, P. A. Golovach, and D. Paulusma. Three complexity results on coloring P_k-free graphs. European Journal of Combinatorics, 34(3):609–619, 2013.
  10. [10]M. Chudnovsky, J. King, M. Pilipczuk, P. Rzążewski, and S. Spirkl. Finding large H-colorable subgraphs in hereditary graph classes. SIAM Journal on Discrete Mathematics, 35(4):2357–2386, 2021.arxiv.org/abs/2004.09425
  11. [11]M. Chudnovsky, R. McCarty, M. Pilipczuk, M. Pilipczuk, and P. Rzążewski. Sparse induced subgraphs in P_6-free graphs. ACM Transactions on Algorithms, 22(2):1–45, 2026.
  12. [12]K. K. Dabrowski, C. Feghali, M. Johnson, G. Paesani, D. Paulusma, and P. Rzążewski. On cycle transversals and their connected variants in the absence of a small linear forest. Algorithmica, 82(10):2841–2866, 2020.arxiv.org/abs/1908.00491
  13. [13]J. Enright and L. Stewart. 3-list colouring permutation graphs. CoRR, abs/1104.5009, 2011.arxiv.org/abs/1104.5009
  14. [14]F. V. Fomin, I. Todinca, and Y. Villanger. Large induced subgraphs via triangulations and CMSO. SIAM Journal on Computing, 44(1):54–87, 2015.
  15. [15]F. V. Fomin and Y. Villanger. Finding induced subgraphs via minimal triangulations. In 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, volume 5 of LIPIcs, pages 383–394. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2010.arxiv.org/abs/0909.5278
  16. [16]J. Gajarský, L. Jaffke, P. T. Lima, J. Masaríková, M. Pilipczuk, P. Rzążewski, and U. S. Souza. Taming graphs with no large creatures and skinny ladders. SIAM J. Discret. Math., 38(4):3140–3149, 2024.
  17. [17]P. Gartland. Quasi-Polynomial Time Techniques for Independent Set and Beyond in Hereditary Graph Classes. PhD thesis, University of California, Santa Barbara, 2023.
  18. [18]P. Gartland and D. Lokshtanov. Independent set on P_k-free graphs in quasi-polynomial time. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, pages 613–624. IEEE, 2020.arxiv.org/abs/2005.00690
  19. [19]P. Gartland and D. Lokshtanov. Graph classes with few minimal separators. I. Finite forbidden induced subgraphs. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, pages 3063–3097. SIAM, 2023.DOI
  20. [20]P. Gartland and D. Lokshtanov. Graph classes with few minimal separators. II. A dichotomy. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, pages 3098–3178. SIAM, 2023.DOI
  21. [21]P. Gartland, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, and P. Rzążewski. Finding large induced sparse subgraphs in Cₜ-free graphs in quasipolynomial time. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pages 330–341. ACM, 2021.arxiv.org/abs/2007.11402
  22. [22]A. Grzesik, T. Klimošová, M. Pilipczuk, and M. Pilipczuk. Polynomial-time algorithm for maximum weight independent set on P₆-free graphs. ACM Transactions on Algorithms, 18(1):4:1–4:57, 2022.
  23. [23]S. Huang, M. Johnson, and D. Paulusma. Narrowing the complexity gap for colouring (Cₛ, Pₜ)-free graphs. The Computer Journal, 58(11):3074–3088, 2015.DOI
  24. [24]K. Jansen and P. Scheffler. Generalized coloring for tree-like graphs. Discrete Applied Mathematics, 75(2):135–155, 1997.
  25. [25]T. Kloks, D. Kratsch, and C. K. Wong. Minimum fill-in on circle and circular-arc graphs. Journal of Algorithms, 28(2):272–289, 1998.
  26. [26]D. Lokshtanov, M. Vatshelle, and Y. Villanger. Independent set in P₅-free graphs in polynomial time. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pages 570–581. SIAM, 2014.
  27. [27]M. Milanič and N. Pivač. Polynomially bounding the number of minimal separators in graphs: Reductions, sufficient conditions, and a dichotomy theorem. Electronic Journal of Combinatorics, 28(1):P1.41, 2021.DOI
  28. [28]M. Pilipczuk, M. Pilipczuk, and P. Rzążewski. Quasi-polynomial-time algorithm for independent set in Pₜ-free graphs via shrinking the space of induced paths. In 4th Symposium on Simplicity in Algorithms, SOSA 2021, pages 204–209. SIAM, 2021.DOI
  29. [29]M. Pilipczuk and P. Rzążewski. A polynomial bound on the number of minimal separators and potential maximal cliques in P₆-free graphs of bounded clique number. Discrete Mathematics & Theoretical Computer Science, 27(2), 2025.DOI
  30. [30]B. Randerath and I. Schiermeyer. 3-colorability ∈ P for P₆-free graphs. Discrete Applied Mathematics, 136(2-3):299–313, 2004.
  31. [31]D. J. Rose. Triangulated graphs and the elimination process. Journal of Mathematical Analysis and Applications, 32(3):597–609, 1970.DOI
  32. [32]W. Unger. On the k-colouring of circle-graphs. In 5th Annual Symposium on Theoretical Aspects of Computer Science, STACS 88, volume 294 of Lecture Notes in Computer Science, pages 61–72. Springer, 1988.
  33. [33]W. Unger. The complexity of colouring circle graphs. In 9th Annual Symposium on Theoretical Aspects of Computer Science, STACS 92, volume 577 of Lecture Notes in Computer Science, pages 389–400. Springer, 1992.
  34. [34]G. J. Woeginger and J. Sgall. The complexity of coloring graphs without long induced paths. Acta Cybernetica, 15(1):107–117, 2001.

Paper details

vlnc:W_6vgsdp5f
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT, Claude

View statement
Looking for related papers…
Contents