Universität zu Köln

Bonomo, Flavia, Chudnovsky, Maria, Maceli, Peter, Schaudt, Oliver, Steinz, Maya and Zhong, Mingxian (2018). Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices. Combinatorica, 38 (4). S. 779 - 802. HEIDELBERG: SPRINGER HEIDELBERG. ISSN 1439-6912

Full text not available from this repository.

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.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Bonomo, Flavia UNSPECIFIED UNSPECIFIED UNSPECIFIED Chudnovsky, Maria UNSPECIFIED UNSPECIFIED UNSPECIFIED Maceli, Peter UNSPECIFIED UNSPECIFIED UNSPECIFIED Schaudt, Oliver UNSPECIFIED UNSPECIFIED UNSPECIFIED Steinz, Maya UNSPECIFIED UNSPECIFIED UNSPECIFIED Zhong, Mingxian UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-177712
DOI:	10.1007/s00493-017-3553-8
Journal or Publication Title:	Combinatorica
Volume:	38
Number:	4
Page Range:	S. 779 - 802
Date:	2018
Publisher:	SPRINGER HEIDELBERG
Place of Publication:	HEIDELBERG
ISSN:	1439-6912
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language NP-COMPLETENESS; COLORING PROBLEMS; K-COLORABILITY; 3-COLORABILITY; COMPLEXITY; TIME Multiple languages Mathematics Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/17771