with(coxeter):
read maxset;
read chrome;
read tight;
read greedy;

# Find colorings for simply-laced graphs
# Select good inner products

gip:=proc(i,j,pr) local c;
  c:=iprod(pr[i],pr[j]); if c<=0 then {i,j} fi;
end:

R:=E8;
interface(quiet=true);
pr:=pos_roots(R): X:={$1..nops(pr)}:
G:={seq(seq(gip(j,i,pr),j=1..i-1),i=1..nops(pr))}: nops(G);
mis:=maxset(G,X): nops(mis);
#  the largest independent set is of size 8
#  this sets mit to be the collection of cardinality-8
#  independent sets ("tight" maximal independent sets).
mit:=map(x->if nops(x)=8 then x fi,mis): nops(mit);
#  runs greedy to get 7 colors.
miu:=maxset(greedy(mit,G,X,8,7)):
sort(convert(map(x->q^nops(x),miu),`+`));
X0:={op(map(op,miu))}: nops(X0)/8;
#  Tries to color what's left.
#  We see below that trying to find an 18-coloring in this manner fails.
st:=time(): k0:=11: chrome(miu,X0,11,'c'), c, .733*(time()-st);
#  However, the following command yields a 12-coloring of what's left,
#  thus a 19-coloring of the whole graph. 
#  st:=time(): k0:=12: chrome(miu,X0,12,'c'), c, .733*(time()-st);
interface(quiet=false);
quit;

# Some other commands which narrow down the range:

# This finds a 20-coloring.  Looking for a 19-coloring
#  in this direct manner was too slow. 
#  st:=time(): chrome(mis,X,20,'c'), c, .733*(time()-st);
#  However, 


# These look for a 15-coloring using only the tight maximal independent sets
#  Since there are 120 positive roots, and the largest independent set has
#  size 8, any 15-coloring must use only the tight maximal independent sets.
#  The first of these commands was too slow to terminate.
#  The second showed that there is no 15-coloring.
#st:=time(): k0:=14: chrome(mit,X,15,'c'), c, .733*(time()-st);
#st:=time(): k0:=15: tight(mit,X,'c'), c, .733*(time()-st);