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;
}