Name
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 \left\{ 5,2\left\lceil \frac{t-1}{2}\right\rceil -2\right\} \) many colors. If the input graph is triangle-free, we only need \(\max \left\{ 4,\left\lceil \frac{t-1}{2}\right\rceil +1\right\} \) many colors. The running time of our algorithm is \(O((3^{t-2}+t^2)m+n)\) if the input graph has n vertices and m edges. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/978-3-319-68705-6_15 | workshop on graph theoretic concepts in computer science |
Keywords | DocType | Volume |
Graph coloring, Forbidden induced paths, Approximation algorithm, 05C69, 05C75, 05C38 | Conference | abs/1606.02967 |
Issue | ISSN | Citations |
8 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 12 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maria Chudnovsky | 1 | 390 | 46.13 |
| Oliver Schaudt | 2 | 95 | 21.74 |
| Sophie Theresa Spirkl | 3 | 8 | 7.36 |
| maya stein | 4 | 81 | 15.65 |
| Mingxian Zhong | 5 | 7 | 4.25 |