List Coloring in the Absence of a Linear Forest

The

k

-

Coloring

problem is to decide whether a graph can be colored with at most

k

colors such that no two adjacent vertices receive the same color. The

List

k

-Coloring

problem requires in addition that every vertex

u

must receive a color from some given set

L

(

u

) ⊆ {1,…,

k

}. Let

P

n

denote the path on

n

vertices, and

G

 + 

H

and

rH

the disjoint union of two graphs

G

and

H

and

r

copies of

H

, respectively. For any two fixed integers

k

and

r

, we show that

List

k

-Coloring

can be solved in polynomial time for graphs with no induced

rP

1

 + 

P

5

, hereby extending the result of Hoàng, Kamiński, Lozin, Sawada and Shu for graphs with no induced

P

5

. Our result is tight; we prove that for any graph

H

that is a supergraph of

P

1

 + 

P

5

with at least 5 edges, already

List

5

-Coloring

is NP-complete for graphs with no induced

H

. We also show that

List

k

-Coloring

is fixed parameter tractable in

k

 + 

r

on graphs with no induced

rP

1

 + 

P

2

, and that

k

-

Coloring

restricted to such graphs allows a polynomial kernel when parameterized by

k

. Finally, we show that

List

k

-Coloring

is fixed parameter tractable in

k

for graphs with no induced

P

1

 + 

P

3

.