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 language | English (US) |
---|---|
Pages | 1239-1256 |
Number of pages | 18 |
State | Published - 2019 |
Event | 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, United States Duration: Jan 6 2019 → Jan 9 2019 |
Conference
Conference | 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 |
---|---|
Country/Territory | United States |
City | San Diego |
Period | 1/6/19 → 1/9/19 |
All Science Journal Classification (ASJC) codes
- Software
- General Mathematics