graph coloring

graph coloring

I had this idea for formatting graph coloring as an LP problem. Too bad it doesn’t work. Here’s a connected graph of three vertices: x1, x2, and x3.
I want to find a color assignment that uses the least number of distinct colors such that no two adjacent vertices have the same color.

x1 ---- x2
 \      /
  \    /
   \  /
    x3

example.lp

Minimize
 obj: + x1 + x2 + x3

Subject To
 c1: + x1 - x2 >= 1
 c2: + x1 - x3 >= 1
 c3: + x2 - x3 >= 1

Bounds
 x1 >= 0
 x2 >= 0
 x3 >= 0

End

It works for this connected graph, but would give a terrible answer for a graph that was just a long string of vertices:
x1 —- x2 —- x3 —- x4

I did this mainly as a demo of the GNU lp kit. Try some linear programs for yourself.

apt install glpk
glpsol -lp example.lp > example_output.txt

Welsh Powell graph coloring implementation

#include<iostream>
#include<algorithm>
#include<stdlib.h>

#define REP(i, n) for(int i = 0;i < n;++i)
#define REP2(i, s, f) for(int i = s;i <= f;++i)

#define ll long long
#define ull unsigned long long

using namespace std;

struct p {
	int first, second;
	bool operator<(const p& o) const {
		return first < o.first;
	}
};

const int N = 100;
const int M = N * (N - 1) / 3;

bool A[N][N];

int D[N]; // D[i] = degree of vertex i
p order[N];

int C[N]; // C[i] = color of vertex i

int main() {

	// create random graph
	srand(2024);
	int a, b;
	REP(i, M) {
		a = rand() % N;
		b = rand() % N;
		while (a == b || A[a][b]) {
			a = rand() % N;
			b = rand() % N;
		}
		A[a][b] = true;
		A[b][a] = true;
	}
	
	// get degree of each vertex
	REP(i, N) {
		REP(j, N) D[i] += A[i][j];
	}
	
	
	

	REP(i, N) {
		order[i].second = i;
		order[i].first = D[i];
	}

	// sort vertices by degree
	sort(order, order + N);
	


	int chromatic = 1;
	
	bool adj[N];

	for (int i = N - 1;i >= 0;--i) {
		int u = order[i].second;
		
		REP(j, N) adj[j] = false;

		REP(v, N) {
			if (u != v && A[u][v]) adj[C[v]] = true;
		}

		int c = 1;
		while (adj[c]) ++c;


		C[u] = c;

		if (c > chromatic) chromatic = c;
	}

	REP(i, N) cout << i << ' ' << C[i] << '\n';
	cout << chromatic << endl;
}