Abstract: The chromatic sum $\Sigma(G)$ of a graph $G$ is the smallest sum of colors among proper colorings using natural numbers. In this paper, we introduce a necessary condition for the existence of graph homomorphisms. Also, we present $\Sigma(G) < \chi_f(G)|G|$ as a tighter upper bound for the chromatic sum.
Introduction
In graph theory, the standard chromatic number $\chi(G)$ identifies the minimum number of colors required to ensure no two adjacent vertices share the same color. However, in many practical applications—such as scheduling or resource allocation—the specific labels assigned to these colors carry weight. The chromatic sum, denoted as $\Sigma(G)$, represents the minimum total cost when colors are represented by natural numbers ($1, 2, 3, \dots$). This metric is particularly relevant for minimizing total delay or expenditure in systems where colors represent time slots or cost tiers.
This paper by Alishahi and Taherkhani (2009) explores the relationship between chromatic sums and graph mappings. The authors provide two primary contributions: a new necessary condition for graph homomorphisms and a refined upper bound for the chromatic sum based on the fractional chromatic number $\chi_f(G)$.
Necessary Conditions for Graph Homomorphisms
A graph homomorphism $\sigma: G \to H$ is a structure-preserving map from the vertex set of $G$ to the vertex set of $H$. Determining whether such a mapping exists is generally an NP-hard problem. To simplify this, researchers seek "necessary conditions"—properties that must hold for a homomorphism to be possible.
The authors focus on vertex-transitive graphs, which possess a high degree of symmetry such that every vertex is indistinguishable from any other (e.g., cycles, complete graphs, or the Petersen graph). They establish that the "average color cost" of a graph serves as a critical invariant.
Theorem 1: If $H$ is a vertex-transitive graph and there exists a homomorphism $\sigma: G \to H$, then: $$\frac{\Sigma(G)}{|G|} \leq \frac{\Sigma(H)}{|H|}$$
This theorem provides a powerful filter. If the minimum average color cost of $G$ exceeds that of a symmetric target graph $H$, no homomorphism can exist. The authors demonstrate the utility of this result by proving that no homomorphism exists from the Petersen graph to the circular clique $K_{8/3}$, a conclusion that would otherwise require exhaustive computational search.
Bounding the Chromatic Sum
Calculating the exact value of $\Sigma(G)$ is NP-complete. While greedy algorithms provide some bounds, such as the Thomassen bound ($\Sigma(G) \leq \frac{3}{2}(e+1)$), these can be quite loose. Alishahi and Taherkhani propose a tighter bound by leveraging the fractional chromatic number $\chi_f(G)$.
By utilizing Kneser graphs ($KG(m, n)$)—fundamental structures in the study of fractional coloring—the authors bridge the gap between total coloring costs and fractional properties. Their primary result in this area is a universal upper bound:
Theorem 2: For every graph $G$, $\Sigma(G) < \chi_f(G)|G|$.
This bound is particularly effective for graphs where the gap between the standard chromatic number $\chi(G)$ and the fractional chromatic number $\chi_f(G)$ is large. In such cases, the authors' bound outperforms traditional greedy limits by an arbitrarily large factor as the graph size increases.
Conclusion and Open Problems
The work demonstrates that the fractional chromatic number provides a significantly more accurate "ceiling" for coloring costs than previously recognized. However, the study also highlights areas for further refinement. The proof for Theorem 2 relies on the upper bound of the chromatic sum of Kneser graphs, but the exact value of $\Sigma(KG(m, n))$ remains unknown. The authors pose the determination of this exact value as an open problem, suggesting that its resolution would lead to even more precise bounds for the chromatic sum of all graphs.
Summary updated