Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs

DOI10.1007/978-3-642-35843-2_29zbMath1303.68074arXiv1202.4665OpenAlexW2401220501MaRDI QIDQ2927657

George B. Mertzios, Paul G. Spirakis

Publication date: 4 November 2014

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1202.4665

zbMATH Keywords

NP-complete3-coloringexponential time hypothesisgraph diametergraph radiussubexponential algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Building a maximal independent set for the vertex-coloring problem on planar graphs, A heuristic for the coloring of planar graphs, List coloring in the absence of two subgraphs, On the complexity of computing treebreadth, Open Problems on Graph Coloring for Special Graph Classes