All graphs in this paper are finite and simple. We use [k] to denote the set {1, . . . , k}. Let G be a graph. A k-coloring of G is a function f : V (G) → [k] such that for every edge uv ∈ E(G), f (u) = f (v), and G is k-colorable if G has a k-coloring. The k-coloring problem is the problem of deciding, given a graph G, if G is k-colorable. This problem is well-known to be N P -hard for all k ≥ 3.
A function L : V (G) → 2 [k] that assigns a subset of [k] to each vertex of a graph G is a k-list assignment for G. For a k-list assignment L, a function f : V (G) → [k] is a coloring of (G, L) if f is a k-coloring of G and f (v) ∈ L(v) for all v ∈ V (G). We say that a graph G is L-colorable, and that the pair (G, L) is colorable, if (G, L) has a coloring. The list-k coloring problem is the problem of deciding, given a graph G and a k-list assignment L, if (G, L) is colorable. Since this generalizes the k-coloring problem, it is also N P -hard for all k ≥ 3.
We denote by P t the path with t vertices and we use K 1,s to denote the complete bipartite graph with parts of size 1 and s respectively. The one-subdivision of K 1,s is obtained by replacing every edge {u, v} of K 1,s by two edges {u, w} and {v, w} with a new vertex w. For a set H of graphs, a graph G is H-free if no element of H is an induced subgraph of G. If H = {H}, we say that G is H-free. In this paper, we use the terms "polynomial time" and "polynomial size" to mean "polynomial in |V (G)|", where G is the input graph. Since the k-coloring problem and the list-k coloring problem are N P -hard for k ≥ 3, their restrictions to H-free graphs, for various H, have been extensively studied. In particular, the following is known: Theorem 1 ( [6]). Let H be a (fixed) graph, and let k > 2. If the k-coloring problem can be solved in polynomial time when restricted to the class of H-free graphs, then every connected component of H is a path.
Thus if we assume that H is connected, then the question of determining the complexity of kcoloring H-free graph is reduced to studying the complexity of coloring graphs with certain induced paths excluded, and a significant body of work has been produced on this topic. Below we list a few such results.
). The 3-coloring problem can be solved in polynomial time for the class of P 7 -free graphs.
). The 4-coloring problem can be solved in polynomial time for the class of P 6 -free graphs.
). The k-coloring problem can be solved in polynomial time for the class of P 5 -free graphs.
). The 4-coloring problem is N P -complete for the class of P 7 -free graphs.
). For all k ≥ 5, the k-coloring problem is N P -complete for the class of P 6 -free graphs.
The only case for which the complexity of k-coloring P t -free graphs is not known k = 3, t ≥ 8. In this paper, we consider the list-3 coloring problem for P t -free graphs with no induced 1subdivision of K 1,s . We use SDK s to denote the one-subdivision of K 1,s . The main result is the following: Theorem 7. For all positive integers s and t, the list-3 coloring problem can be solved in polynomial time for the class of (P t , SDK s )-free graphs.
We need two theorems: the first one is the famous Ramsey Theorem [7], and the second is a result of Edwards [3]: Theorem 8 ( [7]). For each pair of positive integers k and l, there exists an integer R(k, l) such that every graph with at least R(k, l) vertices contains a clique with at least k vertices or an independent set with at least l vertices.
Theorem 9 ( [3]). Let G be a graph, and let L be a list assignment for G such that |L(v)| ≤ 2 for all v ∈ V (G). Then a coloring of (G, L), or a determination that none exists, can be obtained in time
Let G be a graph with list assignment L. For X ⊆ V (G) we denote by G|X the subgraph induced by G on X, by G \ X the graph G|(V (G) \ X) and by (G|X, L) the list coloring problem where we restrict the domain of the list assignment L to X. For v ∈ V (G) we write N G (v) (or N (v) when there is no danger of confusion) to mean the set of vertices of G that are adjacent to v. For X ⊆ V (G) we write N G (X) (or N (X) when there is no danger of confusion) to mean v∈X N (v). We say that D ⊆ V (G) is a dominating set of G if for every vertex v ∈ G \ D, N (v) ∩ D = ∅. By Theorem 9, the following corollary immediately follows.
Corollary 10. Let G be a graph, L be a 3-list assignment for G and let D be a dominating set of G. Then a coloring of (G, L), or a determination that (G, L) is not colorable, can be
Let s and t be positive integers, and let G = (V, E) be a connected (P t , SDK s , K 4 )-free graph. Pick an arbitrary vertex a ∈ V and let S 1 = {a}. For v ∈ V , let d(v) be the distance from v to a. For i = 1, 2, . . . , t -2, we define the set S i+1 as follows:
• For j = 1, 2, . . . , |S i |, let X j i ⊆ B j i be a minimal vertex set such that for every w
It is clear that we can compute S t-1 in O(t|V | 2 ) time. Next, we prove some properties of this construction.
, . . . , x K }. By the minimality of X i , for j = 1, 2, . . . , K, there exists y j ∈ W i such that N (y j ) ∩ X i = {x j }. Since G is K 4free, by Theorem 8, there exists a stable set X ⊆ X i of size R(4, s). We may assume X = {x 1 , x 2 , . . . , x R(4,s) }. Let Y = {y 1 , y 2 , . . . , y R(4,s) }. Again by Theorem 8, there exists a stable set Y ⊆ Y of size s. We may assume Y = {y 1 , y 2 , . . . , y s } and let X = {x 1 , x 2 , . . . , x s }. Then G[{v } ∪ X ∪ Y ] is isomorphic to SDK s , a contradiction. Lemma 12. For i = 0, 1, 2, . . . , t -2, B i+1 \ (B i ∪ S i ) = {v : d(v) = i + 1} (where S 0 = ∅, B 0 = {a} and B t-1 = N (S t-1 )).
Proof. We use induction to prove this lemma. It is clear that for i = 0, B 1 = N (a) = {v : d(v) = 1}. Now suppose this lemma holds for i < k, where k ∈ {1, 2 . . . , t -2}. First we show that for every
, and therefore v ∈ B k+1 , as required. This finishes the proof of Lemma 12.
By applying Lemma 11 and Lemma 12, we deduce several properties of S t-1 .
Lemma 13.
1. There exists a constant M s,t which only depends on s and t such that |S t-1 | ≤ M s,t .
2. W t-1 = V \ (S t-1 ∪ N (S t-1 )) = ∅.
Proof. Since we start with |S 1 | = 1, by applying Lemma 11 t -2 times, it follows that |S t-1 | ≤ (1 + R(4, R(4, s))) t-2 . Let M s,t = (1 + R(4, R(4, s))) t-2 , then the first claim holds.
Suppose the second claim does not hold. From Lemma 12, it follows that {v : d(v) ≤ t -1} ⊆ S t-1 ∪ N (S t-1 ). But if w ∈ V satisfies d(w) ≥ t -1, then a shortest w-a-path is an induced path of length at least t, a contradiction. Thus the second claim holds.