@inproceedings{d3d8153503f94c21b004493f63d0fb04,
title = "Coloring graphs with forbidden induced subgraphs",
abstract = "Since graph-coloring is an NP-complete problem in general, it is natural to ask how the complexity changes if the input graph is known not to contain a certain induced subgraph H. Results of Kam{\'i}nski and Lozin, Holyer, and Levin and Galil imply that the problem remains NP-complete, unless H is the disjoint union of paths. Recently, the question of coloring graphs that do not contain certain induced paths has received considerable attention. Only one case of that problem remains open for k-coloring when k ≥ 4, and that is the case of 4-coloring graphs with no induced 6-vertex path. However, little is known for 3-coloring. In this paper we survey known results on the topic, and discuss recent developments.",
keywords = "Coloring algorithms, Graph coloring, Induced subgraphs",
author = "Maria Chudnovsky",
note = "Publisher Copyright: {\textcopyright} 2014 by Seoul ICM 2014 Organizing Committee. All rights reserved.; 2014 International Congress of Mathematicans, ICM 2014 ; Conference date: 13-08-2014 Through 21-08-2014",
year = "2014",
language = "English (US)",
series = "Proceeding of the International Congress of Mathematicans, ICM 2014",
publisher = "KYUNG MOON SA Co. Ltd.",
pages = "291--302",
editor = "Jang, {Sun Young} and Kim, {Young Rock} and Dae-Woong Lee and Ikkwon Yie and Kim, {Young Rock} and Dae-Woong Lee and Ikkwon Yie",
booktitle = "Invited Lectures",
}