We consider the problem of testing 3-colorability in the bounded-degree model.

We show that, for small enough \varepsilon, every tester for 3-colorability must have query complexity \Omega \text{(n)}. This is the first linear lower bound for testing a natural graph property in the bounded-degree model. An \Omega (\sqrt n ) lower bound was previously known.

For one-sided error testers, we also show an \Omega \text{(n)} lower bound for testers that distinguish 3-colorable graphs from graphs that are({\raise0.7ex\hbox{$1$} \!\mathord{\left/ {\vphantom {1 3}}\right.\kern-\nulldelimiterspace} \!\lower0.7ex\hbox{$3$}} - \alpha )- far from 3-colorable, for arbitrarily small \alpha. In contrast a polynomial time algorithm by Frieze and Jerrum distinguishes 3-colorable graphs from graphs that are {1 \mathord{\left/ {\vphantom {1 5}} \right. \kern-\nulldelimiterspace} 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.