Checking for $3$-colorability by searching for $K_4$ as a minor
Hadwiger's conjecture states that if a graph is not $(k-1)$-colorable then it has a $K_k$ minor. Hadwiger himself proved it for $k \leq 4$. Thus, any graph which is not $3$-colorable has a $K_4$ minor. However, the converse doesn't hold: some graphs having a $K_4$ minor are $3$-colorable. For example, take $K_4$ and split each edge into a path of length $2$ edges. The result is bipartite, and so $2$-colorable.