function [C, n] = color(G)
% Graphtheo project - 2013
% returns a coloration of the graph G
% uses the Welsh-Powell algorithm
% also returns the number of colors used.
% coded with Dylan Werner-Meier.
l = length(G);
% sort the nodes by their degree
[~,S] = sort(sum(G), 'descend');
C = zeros(1, l);
n = 0; % color number
while(any(~C)) % while there is an uncolored node.
n += 1;
% uncolored nodes sorted with S.
V = S(C(S) == 0);
u = V(1);
voisins = G(u,:);
stable = [u];
for v = V % each uncolored node
if(~voisins(v)) % also nonadjacent to the others
stable = [stable v]; % is added.
voisins |= G(v,:);
endif
endfor
C(stable) = n;
endwhile
endfunction