TY - GEN

T1 - Approximately coloring graphs without long induced paths

AU - Chudnovsky, Maria

AU - Schaudt, Oliver

AU - Spirkl, Sophie

AU - Stein, Maya

AU - Zhong, Mingxian

N1 - Funding Information:
M. Chudnovsky—Supported by NSF grant DMS-1550991. S. Spirkl—Supported by Fondecyt grant 1140766 and Millennium Nucleus Information and Coordination in Networks.
Publisher Copyright:
© 2017, Springer International Publishing AG.

PY - 2017

Y1 - 2017

N2 - 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-12⌉-2} many colors. If the input graph is triangle-free, we only need max{4,⌈t-12⌉+1} many colors. The running time of our algorithm is O((3 t - 2+ t2) m+ n) if the input graph has n vertices and m edges.

AB - 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-12⌉-2} many colors. If the input graph is triangle-free, we only need max{4,⌈t-12⌉+1} many colors. The running time of our algorithm is O((3 t - 2+ t2) m+ n) if the input graph has n vertices and m edges.

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

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

U2 - 10.1007/978-3-319-68705-6_15

DO - 10.1007/978-3-319-68705-6_15

M3 - Conference contribution

AN - SCOPUS:85034020956

SN - 9783319687049

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 193

EP - 205

BT - Graph-Theoretic Concepts in Computer Science - 43rd International Workshop, WG 2017, Revised Selected Papers

A2 - Woeginger, Gerhard J.

A2 - Bodlaender, Hans L.

PB - Springer Verlag

T2 - 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2017

Y2 - 21 June 2017 through 23 June 2017

ER -