Algorithms and Almost Tight Results for $$3$$ 3 -Colorability of Small Diameter Graphs
Algorithms and Almost Tight Results for $$3$$ 3 -Colorability of Small Diameter Graphs
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 …