List-three-coloring P_t-free graphs with no induced 1-subdivision of K_1,s
share
Let s and t be positive integers. We use P_t to denote the path with t vertices and 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. In this paper, we give a polynomial-time algorithm for the list-three-coloring problem restricted to the class of P_t-free graph with no induced 1-subdivision of K_1,s.
READ FULL TEXT