Approximately Coloring Graphs Without Long Induced Paths

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

doi:10.1007/s00453-019-00577-6

Approximately Coloring Graphs Without Long Induced Paths

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

Mathematics

Research output: Contribution to journal › Article › peer-review

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

Original language	English (US)
Pages (from-to)	3186-3199
Number of pages	14
Journal	Algorithmica
Volume	81
Issue number	8
DOIs	https://doi.org/10.1007/s00453-019-00577-6
State	Published - Aug 1 2019

All Science Journal Classification (ASJC) codes

General Computer Science
Computer Science Applications
Applied Mathematics

Keywords

Approximation algorithm
Forbidden induced paths
Graph coloring

Access to Document

10.1007/s00453-019-00577-6

Cite this

@article{2f57f311590e4106b1bd83febca8260a,

title = "Approximately Coloring Graphs Without Long Induced Paths",

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.",

keywords = "Approximation algorithm, Forbidden induced paths, Graph coloring",

author = "Maria Chudnovsky and Oliver Schaudt and Sophie Spirkl and Maya Stein and Mingxian Zhong",

note = "Publisher Copyright: {\textcopyright} 2019, Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2019",

month = aug,

day = "1",

doi = "10.1007/s00453-019-00577-6",

language = "English (US)",

volume = "81",

pages = "3186--3199",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "8",

}

TY - JOUR

T1 - Approximately Coloring Graphs Without Long Induced Paths

AU - Chudnovsky, Maria

AU - Schaudt, Oliver

AU - Spirkl, Sophie

AU - Stein, Maya

AU - Zhong, Mingxian

PY - 2019/8/1

Y1 - 2019/8/1

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.

KW - Approximation algorithm

KW - Forbidden induced paths

KW - Graph coloring

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

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

U2 - 10.1007/s00453-019-00577-6

DO - 10.1007/s00453-019-00577-6

M3 - Article

AN - SCOPUS:85065170186

SN - 0178-4617

VL - 81

SP - 3186

EP - 3199

JO - Algorithmica

JF - Algorithmica

IS - 8

ER -

Approximately Coloring Graphs Without Long Induced Paths

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this