Decompression from vector of colors?

[gdalle]

Will never be used in practice with GreedyColoringAlgorithm, but one could imagine optimal colorings with JuMP, which would only output a vector of colors.

71 contains a LinearSystemColoringResult, which is part of the answer in the symmetric case.

[gdalle]

For star and acyclic colorings, we can actually reverse-engineer the set of stars / trees because they are 2-colored!!

[amontoison]

Is it not possible that a color is used in different stars? For the acyclic coloring, a color can be used in different trees.

[gdalle]

Yes, but if we iterate over all pairs of colors we get each tree or star exactly once. Quoting from the decompression paper:

A star coloring of a graph is a distance-1 coloring where, in addition, every path in the graph on four vertices (P4) is required to use at least three colors. An acyclic coloring of a graph is a distance-1 coloring with the further restriction that every cycle in the graph uses at least three colors. The names star and acyclic coloring are due to the structure of twocolored induced subgraphs. In a star-colored graph, a subgraph induced by any two color classes—sets of vertices having the same color—is a collection of stars. A star is a complete bipartite graph in which one of the vertex sets consists of a single vertex, called the hub. The other vertices of the star are spokes. An edge is a degenerate case of a star, in which one vertex is the hub and the other, the spoke, assigned arbitrarily. Similarly, in an acyclically colored graph, a subgraph induced by any two color classes is a collection of trees, and thus acyclic.