Four-coloring P6-free graphs

Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong

Research output: Contribution to conferencePaperpeer-review

19 Scopus citations


In this paper we present a polynomial time algorithm for the 4-coloring problem and the 4-precoloring extension problem restricted to the class of graphs with no induced six-vertex path, thus proving a conjecture of Huang. Combined with previously known results this completes the classification of the complexity of the 4-coloring problem for graphs with a connected forbidden induced subgraph.

Original languageEnglish (US)
Number of pages18
StatePublished - 2019
Event30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, United States
Duration: Jan 6 2019Jan 9 2019


Conference30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
Country/TerritoryUnited States
CitySan Diego

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics


Dive into the research topics of 'Four-coloring P6-free graphs'. Together they form a unique fingerprint.

Cite this