Improved Lower Bounds for Sum Coloring via Clique Decomposition

Qinghua Wu, Jin-Kao Hao

Given an undirected graph $G=(V,E)$ with a set $V$ of vertices and a set $E$ of edges, the minimum sum coloring problem (MSCP) is to find a legal vertex coloring of $G$, using co…