Four-coloring P6-free graphs

Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong

Research output: Contribution to conferencePaper

6 Scopus citations

Abstract

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)
Pages1239-1256
Number of pages18
StatePublished - Jan 1 2019
Event30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, United States
Duration: Jan 6 2019Jan 9 2019

Conference

Conference30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
CountryUnited States
CitySan Diego
Period1/6/191/9/19

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Four-coloring P<sub>6</sub>-free graphs'. Together they form a unique fingerprint.

  • Cite this

    Chudnovsky, M., Spirkl, S., & Zhong, M. (2019). Four-coloring P6-free graphs. 1239-1256. Paper presented at 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, United States.