Optimal proper coloring, chromatic number, fractional chromatic number

[dstahlke]

Graphs.jl has greedy_color, which returns a proper coloring that may not be optimal. It lacks any function that can generate a coloring using the minimum number of colors (the chromatic number). I have a simple implementation of this, but it requires the PicoSAT solver. Could this be added to Graphs.jl, or should this live in some other package? There is SimpleGraphAlgorithms.jl, but this is incompatible with the graphs from Graphs.jl (it is possible to convert the graph type, but it'd be great to have something that works natively).

Along similar lines, I could create a function to compute the fractional chromatic number. This again would require a dependency: a linear programming solver. I'm most familiar with Convex.jl, but GLPK would be a smaller dependency.

[gdalle]

The philosophy behind Graphs.jl is to keep dependencies minmal in the core package, and move algorithms that require external solver to satellite packages. There was a proposal to gather all LP-based algorithms (like flows and matchings) within GraphsOptim.jl, but at the moment I don't have time to work on this. Feel free to add a PR there that uses JuMP to model coloring problems!

[dstahlke]

Thanks. I've opened an issue for GraphsOptim.jl: JuliaGraphs/GraphsOptim.jl#5

To help others finding this via google, in case none of this goes into any package, here is the chromatic number implementation: https://gist.github.com/dstahlke/8e4fd40fa845e792ff7cd3f6b4ccb124

PS: what is github.nowall.world? GraphsOptim.jl seems to be listed both there and at github.com. This is the first I've seen of this, and can't find any information on it.

[gdalle]

PS: what is github.nowall.world? GraphsOptim.jl seems to be listed both there and at github.com. This is the first I've seen of this, and can't find any information on it.

Probably a random mirror?

[gdalle]

Also mentioning https://github.com/somacdivad/GraphInvariants.jl/

[gdalle]

Closing to follow up in GraphsOptim