-3
$\begingroup$
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)
            {
                //get adjacent vertex
                int AdjacentVertex = G.Vertices[i].Edges[j];

                //if an adjacent vertex has the same color, increment the 
                //current vertex's color
                if (G.Vertices[i].Color == G.Vertices[AdjacentVertex].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;
}
$\endgroup$
  • 1
    $\begingroup$ What do you think? What did you try and where did you get stuck? $\endgroup$ – Juho Dec 12 '18 at 8:42
  • $\begingroup$ 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 $\endgroup$ – gnasher729 Dec 12 '18 at 8:52
  • $\begingroup$ Just in case you are not aware, debugging-code or checking-my-code is off-topic everywhere in general. $\endgroup$ – Apass.Jack Dec 12 '18 at 20:49
  • $\begingroup$ 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. $\endgroup$ – Apass.Jack Dec 12 '18 at 20:49
  • $\begingroup$ I don't see an algorithm here. All I see is code. $\endgroup$ – Yuval Filmus Dec 13 '18 at 22:20
2
$\begingroup$

Your algorithm is known as greedy coloring. Wikipedia describes the following bipartite graph, on which the algorithm performs particularly badly:

  • 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.