Approximately Coloring Graphs Without Long Induced Paths

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

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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+ t2) m+ n) if the input graph has n vertices and m edges.

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

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Approximation algorithm
  • Forbidden induced paths
  • Graph coloring

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

Cite this