# Given a list of all maximal independent sets in a graph with vertex set X,
# determine if G has a k-coloring, and if so, assign a listing of the color
# classes to args[4]. Note that the indep sets must be sorted in decreasing
# order of size.

# A global variable k0 can be assigned a value so that progress will be
# reported on each choice of "first" color class when (recursively)
# looking for a k0 coloring.

foo:=proc(x,y) if nops(x)>=y then x fi end:

chrome:=proc(mis,X,k) local i,j,l,new,c,m;
  if k>nops(mis) then l:=chrome(mis,X,nops(mis),'c');
      if l then assign(args[4],c) fi; RETURN(l)
    elif k=0 and nops(X)>0 then RETURN(false)
    elif X=mis[1] then assign(args[4],[X]); RETURN(true)
  fi;
  m:=nops(X)-convert([seq(nops(mis[j]),j=1..k-1)],`+`);
  for i to nops(mis)-k+1 do
    new:=map(foo,[op(i+1..nops(mis),mis)],m);
    if nops(new)=0 then break elif k=k0 then lprint(i,time()) fi;
    new:=subs({seq(j=NULL,j=mis[i])},new);
    new:=sort(map(foo,new,m),(x,y)->evalb(nops(x)>=nops(y)));
    j:=2; while j<=nops(new) do
      for l to j-1 do if nops(new[j] minus new[l])=0 then break fi od;
      if l=j then j:=j+1 else new:=subsop(j=NULL,new) fi;
    od;
    if nops(new)>0 and procname(new,X minus mis[i],k-1,'c') then
      assign(args[4],[mis[i],op(c)]); RETURN(true) fi;
    m:=m+nops(mis[i])-nops(mis[i+k-1]);
  od; false
end: