O(V+E) algorithm for computing chromatic number X(g) of a graph instead of brute-force? I came up with this O(V+E) algorithm for calculating the chromatic number X(g) of a graph g represented by an adjacency list:


Initialize an array of integers "colors" with V elements being 1
Using two for loops go through each vertex and their adjacent nodes and for each of the adjacent node g[i][j] where j is adjacent to i, if j is not visited yet increment colors[g[i][j]] by 1. 
After doing this the maximum integer in the array "colors" is the chromatic number of the graph g(if the algorithm works).


Here is my C++ code:

#include &lt;bits/stdc++.h&gt;
using namespace std;

struct graph {
    vector&lt;vector&lt;int&gt;&gt; adjL;
    vector&lt;int&gt; colours;
    vector&lt;bool&gt; vis;
};

int chrNUM(graph&amp; G) {
    int num = 1; 
    for(int i = 1; i &lt; G.adjL.size(); i ++) {
        for(int j = 0; j &lt; G.adjL[i].size(); j ++) {
            if(!G.vis[G.adjL[i][j]]) {
                G.colours[G.adjL[i][j]] ++;
                num = max(num, G.colours[G.adjL[i][j]]);
            }
        }
        G.vis[i] = true;
    }
    return num;
}

void initGET(graph&amp; G, int N, int M) {
    cin &gt;&gt; N &gt;&gt; M;
    G.adjL.assign(N + 1, vector&lt;int&gt;(0));
    G.colours.assign(N + 1, 1);
    G.vis.assign(N + 1, false);
    for(int i = 0; i &lt; M; i ++) {
        int u,v;
        cin &gt;&gt; u &gt;&gt; v;
        G.adjL[u].push_back(v);
        G.adjL[v].push_back(u);
    }
} 

int main() {
    graph g;
    int n;  //number of vertices
    int m;  //number of edges
    initGET(g, n, m);
    cout &lt;&lt; chrNUM(g);
}


I am wondering if there is a flaw? Maybe it works for certain graphs only? Maybe it gives X(g) for smaller graphs but a value higher than X(g) for larger graphs? I found it worked correctly for all the graphs I have tried (up to 20 vertices). I know this is an NP complete problem but I want some counterexamples for my algorithm if possible or an explanation as to why the method won't work. I have also got a recursive (DFS) solution which is a bit different but mostly similar to this. Any ideas?

Thanks in advance!
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.