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

doi:10.1007/s00493-017-3553-8

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

Mathematics

Research output: Contribution to journal › Article › peer-review

60 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 language	English (US)
Pages (from-to)	779-801
Number of pages	23
Journal	Combinatorica
Volume	38
Issue number	4
DOIs	https://doi.org/10.1007/s00493-017-3553-8
State	Published - Aug 1 2018

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/s00493-017-3553-8

Cite this

@article{319c1f1068d545369375c081555368db,

title = "Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices",

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

author = "Flavia Bonomo and Maria Chudnovsky and Peter Maceli and Oliver Schaudt and Maya Steinz and Mingxian Zhong",

note = "Publisher Copyright: {\textcopyright} 2018, J{\'a}nos Bolyai Mathematical Society and Springer-Verlag GmbH Germany, part of Springer Nature.",

year = "2018",

month = aug,

day = "1",

doi = "10.1007/s00493-017-3553-8",

language = "English (US)",

volume = "38",

pages = "779--801",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "4",

}

TY - JOUR

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

AU - Bonomo, Flavia

AU - Chudnovsky, Maria

AU - Maceli, Peter

AU - Schaudt, Oliver

AU - Steinz, Maya

AU - Zhong, Mingxian

PY - 2018/8/1

Y1 - 2018/8/1

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

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

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

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

U2 - 10.1007/s00493-017-3553-8

DO - 10.1007/s00493-017-3553-8

M3 - Article

AN - SCOPUS:85019748050

SN - 0209-9683

VL - 38

SP - 779

EP - 801

JO - Combinatorica

JF - Combinatorica

IS - 4

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this