Complexity Of Recognising Complete Multipartite Graphs Short question: Is there a linear time algorithm for recognising complete multipartite graphs? 
 A: Yes, there is an $O(n + m)$-time algorithm to decide whether a given graph $G = (V, E)$ is complete multipartite (or equivalently, $\overline{P_3}$-free).
First, we compute the degree $\deg(v)$ of each vertex $v \in V$ in $O(n + m)$ time.
We then partition $V$ into two sets $V_1$ and $V_2$: $V_1$ is the set of vertices of degree smaller than $n / 2 - 1$ and $V_2 = V \setminus V_1$. If $G$ is complete multipartite, then $V_1$ must be an independent set. Otherwise there is an edge $\{ u, v \}$ such that $u, v \in V_1$ and there is a vertex $v$ not adjacent to $u$ or $w$; the three vertices $u, v, w$ form a $\overline{P_3}$. Thus, $V_1$ is contained in one part of the partition of $G$. In fact, $V_1$ must be one part of the partition of $G$ due to its degree constraint. We can verify in $O(m + n)$ time whether each vertex in $V_1$ is adjacent to all vertices in $V_2$. Now it remains to decide $G - V_1$ is complete multipartite. We do so by computing the complement $G'$ of $G - V_1$: $G - V_1$ is complete multipartite iff $G'$ is $P_3$-free. This requires $O(|V_2|^2)$ time using BFS. Note that $m \ge \frac{1}{2} \sum_{v \in V_2} \deg(v_2) \ge \frac{1}{2} \sum_{v \in V_2} (n / 2 - 1) \ge  \frac{1}{2} |V_2| (n / 2 - 1) \ge O(|V_2|^2)$. Therefore, the overall running time is $O(m + n)$.
