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:
CreatorsEmailORCIDORCID Put Code
Chudnovsky, MariaUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Schaudt, OliverUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Spirkl, SophieUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Stein, MayaUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Zhong, MingxianUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
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:
KeywordsLanguage
NP-COMPLETENESS; COMPLEXITYMultiple languages
Computer Science, Software Engineering; Mathematics, AppliedMultiple languages
Refereed: Yes
URI: http://kups.ub.uni-koeln.de/id/eprint/13430

Downloads

Downloads per month over past year

Altmetric

Export

Actions (login required)

View Item View Item