Algorithms and almost tight results for 3-colorability of small diameter graphs

DOI10.1007/s00453-014-9949-6zbMath1336.68142OpenAlexW1873654474WikidataQ59476848 ScholiaQ59476848MaRDI QIDQ261372

George B. Mertzios, Paul G. Spirakis

Publication date: 23 March 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-014-9949-6

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 (13)

Coloring problems on bipartite graphs of small diameter ⋮ Partitioning \(H\)-free graphs of bounded diameter ⋮ Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter ⋮ Independent feedback vertex sets for graphs of bounded diameter ⋮ 3-coloring \(C_4\) or \(C_3\)-free diameter two graphs ⋮ Colouring graphs of bounded diameter in the absence of small cycles ⋮ Acyclic, star, and injective colouring: bounding the diameter ⋮ Colouring graphs of bounded diameter in the absence of small cycles ⋮ Acyclic, star, and injective colouring: bounding the diameter ⋮ Colouring H-free graphs of bounded diameter. ⋮ Recognizing Graphs Close to Bipartite Graphs ⋮ On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs ⋮ Faster 3-Coloring of Small-Diameter Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of surjective homomorphism problems-a survey
• Exact exponential algorithms.
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• The complexity of colouring problems on dense graphs
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Which problems have strongly exponential complexity?
• Transversal numbers of uniform hypergraphs
• 3-colouring AT-free graphs in polynomial time
• Dominating set based exact algorithms for \(3\)-coloring
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Three Complexity Results on Coloring P k -Free Graphs
• The NP-Completeness of Edge-Coloring
• The Diameter of Random Graphs
• 3-coloring in time
• On the complexity of \(k\)-SAT

This page was built for publication: Algorithms and almost tight results for 3-colorability of small diameter graphs