O(V+E) algorithm for computing chromatic number X(g) of a graph instead of brute-force?

Question

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:

1. Initialize an array of integers "colors" with V elements being 1
2. 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.
3. 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 <bits/stdc++.h>
using namespace std;

struct graph {
    vector<vector<int>> adjL;
    vector<int> colours;
    vector<bool> vis;
};

int chrNUM(graph& G) {
    int num = 1; 
    for(int i = 1; i < G.adjL.size(); i ++) {
        for(int j = 0; j < 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& G, int N, int M) {
    cin >> N >> M;
    G.adjL.assign(N + 1, vector<int>(0));
    G.colours.assign(N + 1, 1);
    G.vis.assign(N + 1, false);
    for(int i = 0; i < M; i ++) {
        int u,v;
        cin >> u >> 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 << 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!

Answer 1

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.