List-three-coloring Pt P_t -free graphs with no induced 1-subdivision of K1,s K_{1,s}

preprint2020arXivOpen access

Abstract

Let ss and tt be positive integers. We use PtP_t to denote the path with tt vertices and K1,sK_{1,s} to denote the complete bipartite graph with parts of size 11 and ss respectively. The one-subdivision of K1,sK_{1,s} is obtained by replacing every edge {u,v}\{u,v\} of K1,sK_{1,s} by two edges {u,w}\{u,w\} and {v,w}\{v,w\} with a new vertex ww. In this paper, we give a polynomial-time algorithm for the list-three-coloring problem restricted to the class of PtP_t-free graph with no induced 1-subdivision of K1,sK_{1,s}.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.