List 3-coloring Pt-free graphs with no induced 1-subdivision of K1,s

Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


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.

Original languageEnglish (US)
Article number112086
JournalDiscrete Mathematics
Issue number11
StatePublished - Nov 2020

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


  • Coloring
  • Dominating set
  • Forbidden induced subgraphs


Dive into the research topics of 'List 3-coloring Pt-free graphs with no induced 1-subdivision of K1,s'. Together they form a unique fingerprint.

Cite this