### 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-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}+ t^{2}) m+ n) if the input graph has n vertices and m edges.

Original language | English (US) |
---|---|

Title of host publication | Graph-Theoretic Concepts in Computer Science - 43rd International Workshop, WG 2017, Revised Selected Papers |

Editors | Gerhard J. Woeginger, Hans L. Bodlaender |

Publisher | Springer Verlag |

Pages | 193-205 |

Number of pages | 13 |

ISBN (Print) | 9783319687049 |

DOIs | |

State | Published - Jan 1 2017 |

Event | 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2017 - Eindhoven, Netherlands Duration: Jun 21 2017 → Jun 23 2017 |

### Publication series

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

Volume | 10520 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

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

Country | Netherlands |

City | Eindhoven |

Period | 6/21/17 → 6/23/17 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Approximately coloring graphs without long induced paths'. Together they form a unique fingerprint.

## Cite this

Chudnovsky, M., Schaudt, O., Spirkl, S., Stein, M., & Zhong, M. (2017). Approximately coloring graphs without long induced paths. In G. J. Woeginger, & H. L. Bodlaender (Eds.),

*Graph-Theoretic Concepts in Computer Science - 43rd International Workshop, WG 2017, Revised Selected Papers*(pp. 193-205). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10520 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-68705-6_15