math1um / objects-invariants-properties

Objects, Invariants and Properties for Graph Theory (GT) automated conjecturing: in particular with the Sage program CONJECTURING: http://nvcleemp.github.io/conjecturing/
GNU General Public License v3.0
15 stars 6 forks source link

Add invariant: chromatic_sum #505

Open math1um opened 6 years ago

math1um commented 6 years ago

This was discussed at SIAM DM'18.

The chromatic_sum is the smallest sum of vertex labels, when the vertices are labeled with positive integers and adjacent labels are labeled with different integers ("colors").

See: https://en.wikipedia.org/wiki/Sum_coloring

This is intractable, and at least as hard as chromatic_number. A naive algorithm is: find the chromatic number k, then try all possible labels of the vertices with 1,2..,k, check if its a proper coloring, compute the sum, and store the current minimum.

yirkajk commented 6 years ago

That naive algorithm is in fact not slow enough 😞. According to the wiki, achieving the unique chromatic sum may require more labels than the chromatic number. So, we would have to check even more than 1,2,..,k.