Four-coloring P6-free graphs

Maria Chudnovsky; Sophie Spirkl; Mingxian Zhong

Four-coloring P₆-free graphs

Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong

Mathematics

Research output: Contribution to conference › Paper › peer-review

16 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 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
Mathematics(all)

Cite this

@conference{37fff9b67d224b5294c6b1633d40805d,

title = "Four-coloring P6-free graphs",

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.",

author = "Maria Chudnovsky and Sophie Spirkl and Mingxian Zhong",

note = "Funding Information: Supported by NSF grant DMS-1550991 and US Army Research Office grant W911NF-16-1-0404. Publisher Copyright: Copyright {\textcopyright} 2019 by SIAM; 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 ; Conference date: 06-01-2019 Through 09-01-2019",

year = "2019",

language = "English (US)",

pages = "1239--1256",

}

TY - CONF

T1 - Four-coloring P6-free graphs

AU - Chudnovsky, Maria

AU - Spirkl, Sophie

AU - Zhong, Mingxian

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85062289200&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85062289200&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:85062289200

SP - 1239

EP - 1256

T2 - 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019

Y2 - 6 January 2019 through 9 January 2019

ER -

Four-coloring P₆-free graphs

Abstract

Conference

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this