TY - JOUR
T1 - List 3-coloring Pt-free graphs with no induced 1-subdivision of K1,s
AU - Chudnovsky, Maria
AU - Spirkl, Sophie
AU - Zhong, Mingxian
N1 - Funding Information:
This paper is partially supported by National Science Foundation, United States of America grant DMS-1763817, U.S. Army Research Office grant W911NF-16-1-0404 and PSC-CUNY Award 3407-00 51, and is based upon work supported by the National Science Foundation, United States of America under Award No. DMS-1802201.
Funding Information:
This paper is partially supported by National Science Foundation, United States of America grant DMS-1763817 , U.S. Army Research Office grant W911NF-16-1-0404 and PSC-CUNY Award 3407-00 51, and is based upon work supported by the National Science Foundation, United States of America under Award No. DMS-1802201 .
Publisher Copyright:
© 2020 Elsevier B.V.
PY - 2020/11
Y1 - 2020/11
N2 - Let s and t be positive integers. We use Pt to denote the path with t vertices and K1,s to denote the complete bipartite graph with parts of size 1 and s respectively. The one-subdivision of K1,s is obtained by replacing every edge {u,v} of K1,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 3-coloring problem restricted to the class of Pt-free graph with no induced 1-subdivision of K1,s.
AB - Let s and t be positive integers. We use Pt to denote the path with t vertices and K1,s to denote the complete bipartite graph with parts of size 1 and s respectively. The one-subdivision of K1,s is obtained by replacing every edge {u,v} of K1,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 3-coloring problem restricted to the class of Pt-free graph with no induced 1-subdivision of K1,s.
KW - Coloring
KW - Dominating set
KW - Forbidden induced subgraphs
UR - http://www.scopus.com/inward/record.url?scp=85089079693&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85089079693&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2020.112086
DO - 10.1016/j.disc.2020.112086
M3 - Article
AN - SCOPUS:85089079693
SN - 0012-365X
VL - 343
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 11
M1 - 112086
ER -