using GraphPlot
using Graphs

g = simple_graph(12,is_directed=false)
E = union([(i,j) for i in 1:4 for j in i+1:4],[(i,j) for i in 5:6, j in [1,4]],[(i,j) for i in 7:8, j in [3,4]],[(i,j) for i in 9:10, j in [2,3]],[(i,j) for i in 11:12, j in [1,2]])
for e in E add_edge!(g,e[1],e[2]) end
gplot(g)

using JuMP
using GLPKMathProgInterface

m = Model(solver=GLPKSolverMIP())
C=collect(1:num_vertices(g)) # colors

@variable(m, c[1:num_vertices(g)], Bin)
@variable(m, x[1:num_vertices(g),C], Bin)

@objective(m, Min, sum(c[i] for i in C))

@constraints(m, begin
    [v in 1:num_vertices(g)], sum(x[v,j] for j in C)==1
    [i in C, e in edges(g)], x[source(e,g),i]+x[target(e,g),i] <= 1
    [i in C], num_vertices(g)*c[i] >= sum(x[v,i] for v in 1:num_vertices(g))
        end)

solve(m)
println("The graph is $(Int(getobjectivevalue(m)))-colorable.")

using Colors
nodefillc = distinguishable_colors(num_vertices(g), colorant"red")
vcolor=copy(nodefillc)
for v=1:num_vertices(g), c in C
    if getvalue(x[v,c])>0.5
        vcolor[v]=nodefillc[c]
    end
end

gplot(g,nodefillc=vcolor)

m = Model(solver=GLPKSolverMIP())
C=collect(1:num_vertices(g)) # colors

@variable(m, c[1:num_vertices(g)], Int)
@variable(m, x[1:num_vertices(g),C], Bin)

@objective(m, Min, sum(c[i] for i in C))

@constraints(m, begin
    [v in 1:num_vertices(g)], sum(x[v,j] for j in C)==1
    [i in C, e in edges(g)], x[source(e,g),i]+x[target(e,g),i] <= 1
    [v in 1:num_vertices(g)], c[v] == sum(i*x[v,i] for i in C)
        end)

solve(m)

# extract the colors
colors=[Int(getvalue(c[i])) for i=1:num_vertices(g)]
println("The graph is $(length(unique(colors)))-colorable.")

nodefillc = distinguishable_colors(num_vertices(g), colorant"blue")
vcolor=copy(nodefillc)
for v=1:num_vertices(g), c in C
    if getvalue(x[v,c])>0.5
        vcolor[v]=nodefillc[c]
    end
end
gplot(g,nodefillc=vcolor)