O(V+E) algorithm for computing chromatic number X(g) of a graph instead of brute-force?
Your algorithm is known as greedy coloring. Wikipedia gives an example of a bipartite graph, the crown graph, where the greedy coloring can produce a coloring using $n/2$ colors (for the worst ordering). For random $G(n,1/2)$ graphs, the greedy coloring typically produces a coloring using double the optimal number of colors.