# Does this algorithm correctly compute the chromatic number of a graph?

int ChromaticNumber(Graph G)
{
for (int i = 0; i < G.Vertices.size(); ++i)
{
//initialize vertex color to 1
++G.Vertices[i].Color;
bool Match = true;

//loop while there is an adjacent vertex with the same color
while (Match)
{
Match = false;
for (int j = 0; j < G.Vertices[i].Edges.size(); ++j)
{

//if an adjacent vertex has the same color, increment the
//current vertex's color
{
++G.Vertices[i].Color;
Match = true;
}
}
}
}

int MaxColor = 0;

//loop to determine the largest color value
for (int i = 0; i < G.Vertices.size(); ++i)
if (G.Vertices[i].Color > MaxColor)
MaxColor = G.Vertices[i].Color;

return MaxColor;
}

• What do you think? What did you try and where did you get stuck? – Juho Dec 12 '18 at 8:42
• Finding whether a planar graph is 3-colourable is NP-complete. And your code makes the unjustified assumption that all colours are initialised to 0, so this fails on a code level – gnasher729 Dec 12 '18 at 8:52
• Just in case you are not aware, debugging-code or checking-my-code is off-topic everywhere in general. – Apass.Jack Dec 12 '18 at 20:49
• Just in case you are not aware, unregistered users might be treated with less enthusiasm by some users. However, do not registered yet if you want to update this question or accept a future answer and if you can keep the cookie to this site, that is basically no closing your browser so that you can access the site as user97664. – Apass.Jack Dec 12 '18 at 20:49
• I don't see an algorithm here. All I see is code. – Yuval Filmus Dec 13 '18 at 22:20

• Vertices: $$x_1,y_1,\ldots,x_n,y_n$$.
• Edges: $$x_i$$ is connected to $$y_j$$ whenever $$i \neq j$$.
• Greedy coloring: $$1, 1, 2, 2, \ldots, n, n$$.
The greedy coloring uses $$n$$ colors, while the graph is bipartite and so 2-colorable.