Coloring graphs with forbidden induced subgraphs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Scopus citations

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

Original languageEnglish (US)
Title of host publicationInvited Lectures
EditorsSun Young Jang, Young Rock Kim, Dae-Woong Lee, Ikkwon Yie, Young Rock Kim, Dae-Woong Lee, Ikkwon Yie
PublisherKYUNG MOON SA Co. Ltd.
Pages291-302
Number of pages12
ISBN (Electronic)9788961058070
StatePublished - 2014
Externally publishedYes
Event2014 International Congress of Mathematicans, ICM 2014 - Seoul, Korea, Republic of
Duration: Aug 13 2014Aug 21 2014

Publication series

NameProceeding of the International Congress of Mathematicans, ICM 2014
Volume4

Conference

Conference2014 International Congress of Mathematicans, ICM 2014
Country/TerritoryKorea, Republic of
CitySeoul
Period8/13/148/21/14

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Coloring algorithms
  • Graph coloring
  • Induced subgraphs

Fingerprint

Dive into the research topics of 'Coloring graphs with forbidden induced subgraphs'. Together they form a unique fingerprint.

Cite this