Approximately coloring graphs without long induced paths

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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)
Title of host publicationGraph-Theoretic Concepts in Computer Science - 43rd International Workshop, WG 2017, Revised Selected Papers
EditorsGerhard J. Woeginger, Hans L. Bodlaender
PublisherSpringer Verlag
Pages193-205
Number of pages13
ISBN (Print)9783319687049
DOIs
StatePublished - Jan 1 2017
Event43rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2017 - Eindhoven, Netherlands
Duration: Jun 21 2017Jun 23 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10520 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other43rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2017
CountryNetherlands
CityEindhoven
Period6/21/176/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