Approximately Coloring Graphs Without Long Induced Paths

Maria Chudnovsky, Oliver Schaudt, Sophie Spirkl, Maya Stein, Mingxian Zhong

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)3186-3199
Number of pages14
Issue number8
StatePublished - Aug 1 2019

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics


  • Approximation algorithm
  • Forbidden induced paths
  • Graph coloring


Dive into the research topics of 'Approximately Coloring Graphs Without Long Induced Paths'. Together they form a unique fingerprint.

Cite this