Universität zu Köln

Chudnovsky, Maria, Schaudt, Oliver, Spirkl, Sophie, Stein, Maya and Zhong, Mingxian (2019). Approximately Coloring Graphs Without Long Induced Paths. Algorithmica, 81 (8). S. 3186 - 3200. NEW YORK: SPRINGER. ISSN 1432-0541

Full text not available from this repository.

Abstract

It is an open problem whether the 3-coloring problem can be solved in polynomial time in the class of graphs that do not contain an induced path on t vertices, for fixed t. We propose an algorithm that, given a 3-colorable graph without an induced path on t vertices, computes a coloring with max 5, 2 t-1 2 -2 many colors. If the input graph is triangle-free, we only need max 4, t-1 2 + 1 many colors. The running time of our algorithm is O((3t-2 + t2) m + n) if the input graph has n vertices and m edges.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Chudnovsky, Maria UNSPECIFIED UNSPECIFIED UNSPECIFIED Schaudt, Oliver UNSPECIFIED UNSPECIFIED UNSPECIFIED Spirkl, Sophie UNSPECIFIED UNSPECIFIED UNSPECIFIED Stein, Maya UNSPECIFIED UNSPECIFIED UNSPECIFIED Zhong, Mingxian UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-134309
DOI:	10.1007/s00453-019-00577-6
Journal or Publication Title:	Algorithmica
Volume:	81
Number:	8
Page Range:	S. 3186 - 3200
Date:	2019
Publisher:	SPRINGER
Place of Publication:	NEW YORK
ISSN:	1432-0541
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language NP-COMPLETENESS; COMPLEXITY Multiple languages Computer Science, Software Engineering; Mathematics, Applied Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/13430