Checking if a graph is bipartite is $O(n)$

Question

It seems to me that checking if a graph is bipartite (or biclique) has deterministic time complexity $O(n)$, where $n=|V|^2$, since we clearly have to iterate over all the elements of the incidence matrix. Is there a formal proof that it's at best linear?

Answer 1

A graph is bipartite iff it is 2-colourable. We can check whether a graph is 2 colourable by the classic greedy algorithm. For each vertex, check all the other vertices and for those that are neighbours, check if any of them are coloured red. If not, colour it red, else green. Clearly this is $O(|V|^2)$.