research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:chita
TitleAlgorithms and almost tight results for 3-colorability of Small Diameter Graphs
Bibtex cite IDRACTI-RU1-2013-43
Booktitle SOFSEM 2013
Series Springer LNCS Proceedings
Year published 2013
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 cannot 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 rst subexponential algorithm for 3-coloring, with complexity 2 O ( p n log n ) , which is asymptotically the same as the currently best known time complexity for the graph isomorphism problem. Furthermore we extend the notion of an articulation vertex to that of an articulation neighborhood , and we provide a polynomial algorithm for 3-coloring on graphs with diameter 2 that have at least one articulation neighborhood. 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 " 2 [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 di erent ampli cation techniques of our hardness results, in order to obtain for every " 2 [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 2 O (min f ; n log g ) 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 rst 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 " 2 [ 1 2 ; 1).
Mertzios, George
Spirakis, Paul
Publication ID1038