Approximately coloring graphs without long induced paths

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

doi:10.1007/978-3-319-68705-6_15

Approximately coloring graphs without long induced paths

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

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 ^- ²+ t²) 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	https://doi.org/10.1007/978-3-319-68705-6_15
State	Published - 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/Territory	Netherlands
City	Eindhoven
Period	6/21/17 → 6/23/17

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-68705-6_15

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

Chudnovsky, Maria ; Schaudt, Oliver ; Spirkl, Sophie et al. / Approximately coloring graphs without long induced paths. Graph-Theoretic Concepts in Computer Science - 43rd International Workshop, WG 2017, Revised Selected Papers. editor / Gerhard J. Woeginger ; Hans L. Bodlaender. Springer Verlag, 2017. pp. 193-205 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a1f830382cff4673847fe24ef30dfed2,

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

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

note = "Publisher Copyright: {\textcopyright} 2017, Springer International Publishing AG.; 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2017 ; Conference date: 21-06-2017 Through 23-06-2017",

year = "2017",

doi = "10.1007/978-3-319-68705-6_15",

language = "English (US)",

isbn = "9783319687049",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "193--205",

editor = "Woeginger, {Gerhard J.} and Bodlaender, {Hans L.}",

booktitle = "Graph-Theoretic Concepts in Computer Science - 43rd International Workshop, WG 2017, Revised Selected Papers",

address = "Germany",

}

Chudnovsky, M, Schaudt, O, Spirkl, S, Stein, M & Zhong, M 2017, Approximately coloring graphs without long induced paths. in GJ Woeginger & HL Bodlaender (eds), Graph-Theoretic Concepts in Computer Science - 43rd International Workshop, WG 2017, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10520 LNCS, Springer Verlag, pp. 193-205, 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2017, Eindhoven, Netherlands, 6/21/17. https://doi.org/10.1007/978-3-319-68705-6_15

Approximately coloring graphs without long induced paths. / Chudnovsky, Maria; Schaudt, Oliver; Spirkl, Sophie et al.
Graph-Theoretic Concepts in Computer Science - 43rd International Workshop, WG 2017, Revised Selected Papers. ed. / Gerhard J. Woeginger; Hans L. Bodlaender. Springer Verlag, 2017. p. 193-205 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10520 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Approximately coloring graphs without long induced paths

AU - Chudnovsky, Maria

AU - Schaudt, Oliver

AU - Spirkl, Sophie

AU - Stein, Maya

AU - Zhong, Mingxian

PY - 2017

Y1 - 2017

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.

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

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

U2 - 10.1007/978-3-319-68705-6_15

DO - 10.1007/978-3-319-68705-6_15

M3 - Conference contribution

AN - SCOPUS:85034020956

SN - 9783319687049

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

SP - 193

EP - 205

BT - Graph-Theoretic Concepts in Computer Science - 43rd International Workshop, WG 2017, Revised Selected Papers

A2 - Woeginger, Gerhard J.

A2 - Bodlaender, Hans L.

PB - Springer Verlag

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

Y2 - 21 June 2017 through 23 June 2017

ER -

Chudnovsky M, Schaudt O, Spirkl S, Stein M, Zhong M. Approximately coloring graphs without long induced paths. In Woeginger GJ, Bodlaender HL, editors, Graph-Theoretic Concepts in Computer Science - 43rd International Workshop, WG 2017, Revised Selected Papers. Springer Verlag. 2017. p. 193-205. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-68705-6_15

Approximately coloring graphs without long induced paths

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this