@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 = "Funding Information: Acknowledgments. Partially supported by NSF grants IIS-1117631 and DMS-1265803. This paper is based on the author{\textquoteright}s joint work with Peter Maceli, Juraj Stacho and Mingxian Zhong. The author is grateful to them, and to Irena Penev, for their careful reading of the present manuscript, and for many helpful suggestions. Juraj Stacho{\textquoteright}s help in surveying previously known results was invaluable. The author also thanks Alex Scott for telling her about the beautiful questions that motivated the research described here. 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",
}