A lower bound for testing 3-colorability in bounded-degree graphs

We consider the problem of testing 3-colorability in the bounded-degree model. We show that, for small enough ε, every tester for 3-colorability must have query complexity Ω(n). This is the first linear lower bound for testing a natural graph property in the bounded-degree model. An Ω(√n) lower bound was previously known. For one-sided error testers, we also show an Ω(n) lower bound for testers that distinguish 3-colorable graphs from graphs that are (1/3 - α)-far from 3-colorable, for arbitrarily small α. In contrast, a polynomial time algorithm by Frieze and Jerrum (1997) distinguishes 3-colorable graphs from graphs that are 1/5-far from 3-colorable. As a by-product of our techniques, we obtain tight unconditional lower bounds on the approximation ratios achievable by sublinear time algorithms for Max E3SAT, Max E3LIN-2 and other problems.