I was trying to understand the underlying difficulty of coloring 3 colorable graphs with as least number of colors as possible. Though i am aware of hardness result of coloring it with 4 colors, i couldn't characterize these graphs much. My question is:
What are the different characteristics of 3 colorable graph? Also what makes them different from 4 colorable graphs (or others), apart from the fact the 3 colorable graphs may not necessarily have $K_4$ as minor whereas 4 colorable graphs will have?
I have tried to work on these but couldn't come with some argument of my own and the materials i got discussed algorithms like $n^{\epsilon}$-approximation through SDP which i have read but still i feel i am lacking the insight to the problem.