GT chromatic patition

 #include <iostream>

#include <list>

using namespace std;

class Graph

{

int V;

list<int> *adj;

public:

Graph(int V)

{

this->V = V;

adj = new list<int>[V];

}

~Graph() { delete[] adj; }

void addEdge(int v, int w);

void greedyColoring();

};

void Graph::addEdge(int v, int w)

{

adj[v].push_back(w);

adj[w].push_back(v);

}

void Graph::greedyColoring()

{

int result[V];

// Assign the first color to first vertex

result[0] = 0;

// Initialize remaining V-1 vertices as unassigned

for (int u = 1; u < V; u++)

result[u] = -1; // no color is assigned to u

bool available[V];

for (int cr = 0; cr < V; cr++)

available[cr] = false;

for (int u = 1; u < V; u++)

{

list<int>::iterator i;

for (i = adj[u].begin(); i != adj[u].end(); ++i)

if (result[*i] != -1)

available[result[*i]] = true;

// Find the first available color

int cr;

for (cr = 0; cr < V; cr++)

if (available[cr] == false)

break;

result[u] = cr; // Assign the found color

// Reset the values back to false for the next iteration

for (i = adj[u].begin(); i != adj[u].end(); ++i)

if (result[*i] != -1)

available[result[*i]] = false;

}

int chromaticNu = 0;

for (int u = 0; u < V; u++)

{

if (result[u] + 1 > chromaticNu)

{

chromaticNu = result[u] + 1;

}

cout << "Vertex " << u << " ---> Color "

<< result[u] + 1 << endl;

}

cout << "Chromatic No is : " << (chromaticNu);

}

int main()

{

Graph g2(3);

g2.addEdge(0, 1);

g2.addEdge(1, 2);

g2.addEdge(0, 2);

cout << "\nColoring of graph 1 \n";

g2.greedyColoring();

Graph g1(4);

g1.addEdge(0, 1);

g1.addEdge(1, 2);

g1.addEdge(2, 3);

g1.addEdge(0, 3);

cout << "\n\nColoring of graph 2 \n";

g1.greedyColoring();

return 0;

}