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

Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong

Research output: Contribution to journalArticle

Abstract

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
Volume343
Issue number11
DOIs
StatePublished - Nov 2020

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Keywords

  • Coloring
  • Dominating set
  • Forbidden induced subgraphs

Fingerprint Dive into the research topics of 'List 3-coloring P<sub>t</sub>-free graphs with no induced 1-subdivision of K<sub>1,s</sub>'. Together they form a unique fingerprint.

  • Cite this