List 3-Coloring Graphs with No Induced P6+ rP3

Maria Chudnovsky, Shenwei Huang, Sophie Spirkl, Mingxian Zhong

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


For an integer t, we let Pt denote the t-vertex path. We write H+ G for the disjoint union of two graphs H and G, and for an integer r and a graph H, we write rH for the disjoint union of r copies of H. We say that a graph G is H-free if no induced subgraph of G is isomorphic to the graph H. In this paper, we study the complexity of k-coloring, for a fixed integer k, when restricted to the class of H-free graphs with a fixed graph H. We provide a polynomial-time algorithm to test if, for fixed r, a (P6+ rP3) -free is three-colorable, and find a coloring if one exists. We also solve the list version of this problem, where each vertex is assigned a list of possible colors, which is a subset of { 1 , 2 , 3 }. This generalizes results of Broersma, Golovach, Paulusma, and Song, and results of Klimošová, Malik, Masařík, Novotná, Paulusma, and Slívová. Our proof uses a result of Ding, Seymour, and Winkler relating matchings and hitting sets in hypergraphs. We also prove that the problem of deciding if a (P5+ P2) -free graph has a k-coloring is NP-hard for every fixed k≥ 5.

Original languageEnglish (US)
Pages (from-to)216-251
Number of pages36
Issue number1
StatePublished - Jan 2021

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics


  • Forbidden induced subgraph
  • Graph coloring
  • Polynomial algorithm


Dive into the research topics of 'List 3-Coloring Graphs with No Induced P6+ rP3'. Together they form a unique fingerprint.

Cite this