Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
Mertzios, G.B.; Spirakis, P.G.
Authors
P.G. Spirakis
Contributors
Peter van Emde Boas
Editor
Frans C.A. Groen
Editor
Giuseppe F. Italiano
Editor
Jerzy Nawrocki
Editor
Harald Sack
Editor
Abstract
The 3-coloring problem is well known to be NP-complete. It is also well known that it remains NP-complete when the input is restricted to graphs with diameter 4. Moreover, assuming the Exponential Time Hypothesis (ETH), 3-coloring can not be solved in time 2 o(n) on graphs with n vertices and diameter at most 4. In spite of the extensive studies of the 3-coloring problem with respect to several basic parameters, the complexity status of this problem on graphs with small diameter, i.e. with diameter at most 2, or at most 3, has been a longstanding and challenging open question. In this paper we investigate graphs with small diameter. For graphs with diameter at most 2, we provide the first subexponential algorithm for 3-coloring, with complexity 2O(nlogn√). Furthermore we present a subclass of graphs with diameter 2 that admits a polynomial algorithm for 3-coloring. For graphs with diameter at most 3, we establish the complexity of 3-coloring, even for the case of triangle-free graphs. Namely we prove that for every ε∈[0,1), 3-coloring is NP-complete on triangle-free graphs of diameter 3 and radius 2 with n vertices and minimum degree δ = Θ(n ε ). Moreover, assuming ETH, we use three different amplification techniques of our hardness results, in order to obtain for every ε∈[0,1) subexponential asymptotic lower bounds for the complexity of 3-coloring on triangle-free graphs with diameter 3 and minimum degree δ = Θ(n ε ). Finally, we provide a 3-coloring algorithm with running time 2O(min{δΔ, nδlogδ}) for arbitrary graphs with diameter 3, where n is the number of vertices and δ (resp. Δ) is the minimum (resp. maximum) degree of the input graph. To the best of our knowledge, this algorithm is the first subexponential algorithm for graphs with δ = ω(1) and for graphs with δ = O(1) and Δ = o(n). Due to the above lower bounds of the complexity of 3-coloring, the running time of this algorithm is asymptotically almost tight when the minimum degree of the input graph is δ = Θ(n ε ), where ε∈[12,1)
Citation
Mertzios, G., & Spirakis, P. (2013). Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs. In P. V. E. Boas, F. C. Groen, G. F. Italiano, J. Nawrocki, & H. Sack (Eds.), SOFSEM 2013 : theory and practice of computer science : 39th international conference on current trends in theory and practice of computer science, Špindlerův Mlýn, Czech Republic, January 26-31, 2013. Proceedings (332-343). Springer Verlag. https://doi.org/10.1007/978-3-642-35843-2_29
Publication Date | 2013 |
---|---|
Deposit Date | Sep 5, 2014 |
Publicly Available Date | Jun 22, 2015 |
Publisher | Springer Verlag |
Pages | 332-343 |
Series Title | Lecture notes in computer science |
Book Title | SOFSEM 2013 : theory and practice of computer science : 39th international conference on current trends in theory and practice of computer science, Špindlerův Mlýn, Czech Republic, January 26-31, 2013. Proceedings. |
ISBN | 9783642358425 |
DOI | https://doi.org/10.1007/978-3-642-35843-2_29 |
Keywords | 3-coloring, Graph diameter, Graph radius, Subexponential algorithm, NP-complete, Exponential time hypothesis. |
Public URL | https://durham-repository.worktribe.com/output/1677798 |
Files
Accepted Book Chapter
(336 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-35843-2_29.
You might also like
Interference-free walks in time: Temporally disjoint paths
(2022)
Journal Article
Equitable scheduling on a single machine
(2022)
Journal Article
The Power of Linear-Time Data Reduction for Maximum Matching
(2020)
Journal Article
When can graph hyperbolicity be computed in linear time?
(2018)
Journal Article
A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
(2018)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2025
Advanced Search