Approximately Coloring Graphs Without Long Induced Paths

Chudnovsky M.; Schaudt O.; Spirkl S.; Stein M.; Zhong M.

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.

Más información

Título según WOS: Approximately Coloring Graphs Without Long Induced Paths
Título según SCOPUS: Approximately Coloring Graphs Without Long Induced Paths
Título de la Revista: ALGORITHMICA
Volumen: 81
Número: 8
Editorial: Springer
Fecha de publicación: 2019
Página de inicio: 3186
Página final: 3199
Idioma: English
DOI:

10.1007/s00453-019-00577-6

Notas: ISI, SCOPUS