# 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:

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<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 ++) {
}
}
G.vis[i] = true;
}
return num;
}

void initGET(graph& G, int N, int M) {
cin >> N >> M;
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;
}
}

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?

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.
• Another simple example is a star graph, where a worst ordering (i.e., center node being last) will lead to a coloring using $n$ colors when the answer is just 2. Dec 27, 2019 at 7:13