Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices

Flavia Bonomo, Maria Chudnovsky, Peter Maceli, Oliver Schaudt, Maya Steinz, Mingxian Zhong

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

Abstract

In this paper we present a polynomial time algorithm that determines if an input graph containing no induced seven-vertex path is 3-colorable. This affirmatively answers a question posed by Randerath, Schiermeyer and Tewes in 2002. Our algorithm also solves the list-coloring version of the 3-coloring problem, where every vertex is assigned a list of colors that is a subset of {1,2,3}, and gives an explicit coloring if one exists.

Original languageEnglish (US)
Pages (from-to)779-801
Number of pages23
JournalCombinatorica
Volume38
Issue number4
DOIs
StatePublished - Aug 1 2018

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices'. Together they form a unique fingerprint.

Cite this