<figure><img src="image_1.png" /></figure>

HAL
open science

# Sum Coloring: New upper bounds for the chromatic strength

Clément Lecat, Corinne Lucet, Chu Min Li

<figure><img src="image_2.png" /></figure>

## To cite this version:

Clément Lecat, Corinne Lucet, Chu Min Li. Sum Coloring: New upper bounds for the chromatic strength. 2016. hal-01321029

HAL Id: hal-01321029

https://hal.science/hal-01321029

Preprint submitted on 24 May 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Sum Coloring : New upper bounds for the chromatic strength

Clément Lecat, Corinne Lucet, Chu-Min Li

Laboratoire de Modélisation, Information et Système EA 4290, Université de Picardie Jules Verne, Amiens, France

## Abstract

The Minimum Sum Coloring Problem (*MSCP*) is derived from the Graph Coloring Problem (*GCP*) by associating a weight to each color. The aim of *MSCP* is to find a coloring solution of a graph such that the sum of color weights is minimum. *MSCP* has important applications in fields such as scheduling and VLSI design. We propose in this paper new upper bounds of the chromatic strength, i.e. the minimum number of colors in an optimal solution of *MSCP*, based on an abstraction of all possible colorings of a graph called motif. Experimental results on standard benchmarks show that our new bounds are significantly tighter than the previous bounds in general, allowing to reduce substantially the search space when solving *MSCP*.

## 1. Introduction

The Graph Coloring Problem (*GCP*) is an important NP-hard combinatorial problem. A lot of effort has been devoted to study it. Two main types of algorithms (also called solvers) are developed for solving *GCP*: exact methods and approximate methods. Exact methods aim at finding an optimal solution of the problem, including the approaches based on branch-and-bound schema [23], on graph decomposition [21], and on SAT solving by encoding the problem into an equivalent propositional formula [30]. The minimum number of colors needed to color a graph *G* is called the *chromatic number* of *G* and is denoted by $\chi(G)$. The approximate methods aim at finding an upper bound or a lower bound of the optimal solution of the problem, including: greedy algorithms such as the famous DSATUR [6], and various heuristic or meta-heuristic algorithms [26, 11, 20]. In the literature, these methods are usually evaluated on standard benchmarks such as DIMACS and COLOR [7, 12].

The Minimum Sum Coloring Problem (*MSCP*) is derived from *GCP* and is introduced in 1989 by Kubicka et Schwenk [16], by associating a weight to each color. The aim of *MSCP* is to find a valid coloring solution that minimizes the sum of color weights. The minimum number of colors in an optimal solution of *MSCP* for a graph *G* is called the *chromatic strength* of *G* and is denoted by $s(G)$. Note that $s(G)$ can be bigger than $\chi(G)$. *MSCP* has important applications in fields such as scheduling, VLSI design and ressource allocation [1, 22]. For example, to calculate the best quality of service in a distributed system with shared resource amounts to solve *MSCP*. The main results on *MSCP* include the theoretical bounds [13, 29, 22, 2] and the structural properties relative to the graph families for which efficient *MSCP* algorithms exist. Recently, heuristics and meta-heuristics for *MSCP* are proposed in [19] and [28, 15, 3, 25] respectively, giving bounds for DIMACS and COLOR graphs, and exact methods are proposed in [17].

When solving *GCP* and *MSCP* for a graph *G*, an algorithm generally has to explore the search space of *GCP* and *MSCP* that grows exponentially with the number of colors to be considered. In practice it is substantially harder to reduce the number of colors to be considered when solving *MSCP* than when solving *GCP*. In fact, for *GCP* when a valid coloring solution with *k* colors is found, the sub-space with *k* or more colors can be pruned. However, this is not the case for *MSCP*, because the optimal solution of *MSCP* can involve more than *k* colors. So, establishing a tight upper bound of $s(G)$ is essential to solve *MSCP*.
Unfortunately, there are few works in the literature allowing to derive a tight upper bound of $s(G)$. The only two existing upper bounds in our knowledge are proposed in [24] and in [9] respectively. In this paper, we propose two new upper bounds of $s(G)$ by exploring an abstraction of the set of coloring solutions of $G$ called motif. The notion of motif was already used by Bonomo and Valencia-Pabon in [4, 5] to solve MSCP for P$_4$-sparse graphs. However, it is the first time in our knowledge that motifs are used for upper bounding $s(G)$. By skillfully identifying and excluding those motifs that cannot correspond to an optimal solution of MSCP, we derive the two new upper bounds of $s(G)$ from the remaining motifs. The experimental results on standard benchmarks DIMACS and COLOR [7, 12] for coloring problems show that our bounds are substantially better than the existing bound proposed in [9] in general. In some instances, the gain is greater than 200 colors. The other existing bound proposed in [24] is not compared because it is trivial.

This paper is organized as follows. Section 2 presents the preliminaries necessary for our approach. Section 3 presents our approach for identifying the motifs that cannot correspond to an optimal solution of MSCP and for computing the new upper bounds of $s(G)$. Section 4 compares our new upper bounds with the existing bound proposed in [9] on the DIMACS and COLOR graphs. Section 5 concludes.

## 2. Preliminaries

### 2.1. Basic definitions, GCP, MSCP, MaxClique and MaxStable

We consider an undirected graph $G = (V, E)$, where $V$ is a set of vertices ($|V| = n$) and $E \subseteq V^2$ a set of edges. The set of adjacent (or neighbor) vertices of $v \in V$, denoted by $\mathcal{N}$, is defined as : $\mathcal{N}(v) = \{u | (u, v) \in E\}$. The degree $d(v)$ of a vertex $v$ is the number of its adjacent vertices, i.e., $d(v) = |\mathcal{N}(v)|$. The degree of a graph, denoted by $\Delta(G)$, is $\max\{d(v) | v \in V\}$. A clique $C$ is a subset of $V$ such that $\forall u, v \in C$, $(u, v) \in E$. A stable set $S$ is a subset of $V$ such that $\forall u, v \in S$, $(u, v) \notin E$. The complement graph of $G$ is defined as $\bar{G} = (\bar{V}, \bar{E})$ where $\bar{E} = V^2 \setminus E$. A clique in $G$ is a stable set in $\bar{G}$ and vice versa. A graph $G' = (V', E')$ is a subgraph of $G$ induced by $V'$ if $V' \subseteq V$ and $E' = V'^2 \cap E$.

A coloring of a graph $G$ with $k$ colors is a function $c: V \to \{1, 2, \dots, k\}$ that assigns to each vertex $v \in V$ a color $c(v)$. A coloring is valid, if $\forall (u, v) \in E$, $c(u) \neq c(v)$. We denote a coloring of $G$ with $k$ colors by $X = \{X_1, X_2, \dots, X_k\}$, where $X_i = \{v \in V | c(v) = i\}$ is called a color class. The Graph Coloring Problem (GCP) consists in finding a valid coloring $X$ of $G$ with minimum $k$. Such $k$ is called the chromatic number of $G$, and is denoted by $\chi(G)$. GCP is NP-Hard [8].

The Minimum Sum Coloring Problem (MSCP) is derived from GCP by associating a weight $w_i$ with each color $i$. In this paper, we consider $w_i = i$. We denote by $\Sigma(X)$ the sum of color weights of a coloring :

$$ \Sigma(X) = 1 \times |X_1| + 2 \times |X_2| + \dots + k \times |X_k| $$

**Example 1.** Refer to the graph in Figure 1, $X = \{\{a, e\}_1, \{b\}_2, \{c, d, f\}_3\}$ is a valid coloring. The vertices a and e are colored with the color 1, the vertex b with the color 2, and the vertices c, d and f with the color 3. The sum coloring is $\Sigma(X) = 1 \times 2 + 2 \times 1 + 3 \times 3 = 13$.

Given a graph $G$, MSCP consists in finding a valid coloring $X$ of $G$ with the minimum sum of color weights $\Sigma(X)$. This minimum sum is called the chromatic sum of $G$ and is denoted by $\Sigma(G)$ :

$$ \Sigma(G) = \min\{\Sigma(X) \mid X \text{ is a valid coloring of } G\} $$

Kubicka and Schwenk proved that MSCP is NP-Hard [16]. An optimal solution of GCP does not necessarily correspond to an optimal solution for MSCP. For example, the optimal solution of GCP for the graph in Figure 2 uses 2 colors, for which the sum of color weights is 12, while an optimal solution of MSCP for this graph uses 3 colors. The chromatic sum of the graph is 11. The minimum number of
<figure><img src="image_4.png" /><figcaption>FIGURE 1: A simple graph</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>FIGURE 2: An optimal solution for GCP : $X=\{{\{a, b, c, e\}_1, \{d, f, g, h\}_2\}}$ with sum of color weights equal to 12,
and an optimal solution for MSCP : $X'=\{{\{a, b, c, f, g, h\}_1, \{d\}_2, \{e\}_3\}}$ with sum of color weights equal to 11.</figcaption></figure>

colors in an optimal solution of *MSCP* of a graph *G* is called *chromatic strength* (or simply *strength*) of *G*, and is denoted by *s*(*G*).

A valid coloring of a graph $G = (V, E)$ with $k$ colors $c : V \to \{1, 2, \dots, k\}$ is to be found in a set of colorings of cardinality $k^{|V|}$, which forms the search space for both *GCP* and *MSCP*. The number $k$ must be large enough to achieve an optimal solution. While *GCP* and *MSCP* are both NP-hard, *MSCP* is much harder to solve than *GCP* in practice, because it is much more complex to prune search space when solving *MSCP*. So, determining an upper bound of $s(G)$ as tight as possible is essential for solving *MSCP*.

Given a graph $G$, the MaxClique (MaxStable) problem consists in finding a clique (stable set) with the maximum cardinality in $G$. Note that finding a maximum stable set in $G$ is equivalent to finding a maximum clique in $\bar{G}$.

## 2.2. Major coloring

For a given coloring $X$, each color class $X_i$ is a stable set. We can exchange two colors $i$ and $j$ without impacting the validity of $X$. The set of colorings that can be achieved by such exchanges from $X$, are symmetric and form an equivalence class, denoted by $\Theta(X)$. All colorings of $\Theta(X)$ use the same number of colors, but they do not give the same sum of color weights. Refer to Figure 1, the sum of color weights of the coloring $\{{\{a, e\}_1, \{b\}_2, \{c, d, f\}_3\}}$ is 13, while the sum of color weights of the coloring $\{{\{a, e\}_1, \{c, d, f\}_2, \{b\}_3\}}$ is 11. Therefore, we define the notion of major coloring.

**Definition 1.** A major coloring, denoted by $X^m$, is a coloring $X^m = \{X_1, X_2, \dots, X_k\}$ such that $|X_1| \ge |X_2| \ge \dots \ge |X_k|$.

**Example 2.** Refer to Figure 1, the coloring $X = \{{\{c, d, f\}_1, \{a, e\}_2, \{b\}_3\}}$ is a major coloring of the graph.
$\Sigma(X^m) = 10$.

The following property is a direct consequence of Definition 1.
**Property 1.** Let $\Theta(X)$ be the set of symmetric colorings of $X$ and $X^m$ a major coloring of $\Theta(X)$, then $\forall X' \in \Theta(X), \Sigma(X^m) \le \Sigma(X')$.

Consequently, only major colorings need to be considered when solving MSCP. In the sequel, all colorings we consider are major and are simply written as $X$.

### 2.3. Motifs

Any major coloring $X$ with $k$ colors corresponds to a non-increasing sequence $p$ of integers : ($|X_1|, |X_2, \dots, |X_k|$), called the motif of $X$. The $i^{th}$ integer is denoted by $p[i] = |X_i|$.

The sum of color weights of $X$ can be computed as :

$$ \Sigma(X) = \Sigma(p) = 1 \times p[1] + 2 \times p[2] + \dots + k \times p[k] \quad (1) $$

**Example 3.** The motif corresponding to $X = \{\{c, d, f\}_1, \{a, e\}_2, \{b\}_3\}$ is $p = (3, 2, 1)$, with $p[1] = 3, p[2] = 2$ and $p[3] = 1$. $\Sigma(X) = \Sigma(p) = 10$.

The interest of the motif notion is that a motif provides an abstraction of several colorings, that is essential for MSCP. For example, refer to Figure 1, the two different colorings $\{c, d, f\}_1, \{b, e\}_2, \{a\}_3$ and $\{a, e, f\}_1, \{b, c\}_2, \{e\}_3$ can be represented by the same motif $p = (3, 2, 1)$. Two different motifs represent necessarily different colorings. Nevertheless, a motif can represent an invalid coloring, because it does not include any structural property of a graph. For example, refer to Figure 1, the motifs $(5, 1)$ and $(4, 1, 1)$ do not represent any valid coloring of the graph. As we will show in Section 3.4, some characteristics of a graph can be used to exclude a part of motifs representing invalid colorings, so that we can derive interesting properties for MSCP from the remaining motifs. We denote by $\phi(n)$ the set of all motifs for any graph with $n$ vertices, and $\phi(n, k)$ the set of motifs with $k$ colors for any graph with $n$ vertices.

$$ \phi(n, k) = \{p \in \phi(n) \mid |p| = k\} $$

$$ \phi(n) = \bigcup_{k=1}^{n} \{\phi(n, k)\} $$

The number of motifs in $\phi(n)$ is equal to the number of partitions of $n$ into non-increasing integers, which grows exponentially with $n$. Hardy and Ramanujan[10] give an approximate number of partitions of $n$ into non-increasing integers :

$$ |\phi(n)| \sim \frac{1}{4n\sqrt{3}} e^{\pi\sqrt{2n/3}} \quad (2) $$

<table><caption>Table 1 illustrates the exponential growth of the cardinality of $\phi(n)$.</caption><tr><td>n</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td><td>20</td><td>50</td><td>100</td><td>150</td></tr><tr><td>|φ(n)|</td><td>1</td><td>2</td><td>3</td><td>5</td><td>7</td><td>11</td><td>15</td><td>22</td><td>30</td><td>42</td><td>697</td><td>204,226</td><td>190,569,292</td><td>40,853,235,313</td></tr></table>

<caption>TABLE 1: Cardinality of $\phi(n)$.</caption>

Our approach works in $\phi(n)$ to find a tight upper bound of the chromatic strength of any graph with $n$ vertices, using the dominance relation between the motifs defined in the next subsection.

### 2.4. Dominance relation

The dominance relation, denoted by $\succeq$, between the motifs of $\phi(n)$ was introduced by Bonomo and Valencia in [4, 5] to compute the chromatic sum of a subset of $P_4$-sparse graphs, or an upper bound of the chromatic sum for general $P_4$-sparse graphs. We adapt their definition for our approach to derive tight upper bounds of the chromatic strength.
**Definition 2.** Let $p$ and $q$ be two motifs in $\phi(n)$. We say that $p$ dominates $q$, denoted by $p \succeq q$, if and only if $\forall t$ such that $1 \le t \le \min\{|p|, |q|\}$, $\sum_{x=1}^t p[x] \ge \sum_{x=1}^t q[x]$.

The main difference of Definition 2 with the original definition in [4] is that in this paper we explicitly require $\sum_{x=1}^{|p|} p[x] = \sum_{x=1}^{|q|} q[x] = n$, because $p$ and $q$ are both in $\phi(n)$.

Two motifs are not necessarily comparable, as shown in Example 4.

**Example 4.** Let $p$ and $q$ be two motifs of a graph $G$ with 15 vertices, $p = (9, 3, 3)$ and $q = (8, 6, 1)$.

$$ \text{If } t = 1: \sum_{i=1}^{1} p[i] > \sum_{i=1}^{1} q[i] \ (9 > 8). $$

$$ \text{If } t = 2: \sum_{i=1}^{2} p[i] < \sum_{i=1}^{2} q[i] \ (9+3 < 8+6). $$

$p \not\succeq q$ and $q \not\succeq p$, i.e., $p$ and $q$ are not comparable.

So, the dominance relation $\succeq$ is a partial order. It is easy to prove the following property that makes the dominance relation useful for MSCP [4, 5].

**Property 2.** Let $G$ be a graph, $p$ and $q$ two motifs corresponding to two valid colorings $X$ and $X'$ of $G$, respectively. If $p \succeq q$ then $\Sigma(X) \le \Sigma(X')$.

### 3. Tight upper bounds for the chromatic strength

Much effort is spent to establish the relationship between the structural properties of a graph $G$ and its chromatic sum $[2, 27, 14, 5]$. However, less attention is paid to the chromatic strength. Property 3 states a trivial upper bound of $s(G)$ found in [24]:

**Property 3.**

$$ s(G) \le \Delta(G) + 1 $$

A better upper bound based on a valid coloring of $G$ is given in [9] and is stated in Property 4.

**Property 4.** Let $G$ be a graph and $X$ a valid coloring with $k$ colors, then

$$ s(G) \le \left\lceil \frac{\Delta(G) + \chi(G)}{2} \right\rceil \le \left\lceil \frac{\Delta(G) + k}{2} \right\rceil $$

In this section, we propose two new upper bounds of $s(G)$ based on a valid coloring of $G$ by exploring $\phi(n)$. For this purpose, we first present a total order in $\phi(n)$ and an algorithm allowing to assign an index to each motif in $\phi(n, k)$, which is needed for the understanding of the new upper bounds. Then we present the bounds after explaining their principle.

#### 3.1. Establishing a total order in $\phi(n)$

The set of motifs $\phi(n)$ can be sorted in the following order: $\phi(n, 1)$, $\phi(n, 2)$, ..., $\phi(n, n)$, then each $\phi(n, k)$ is sorted in the decreasing lexicographical order. As an example, Table 2 lists all motifs in $\phi(8)$ in the above order.

Algorithm 1 generates the motifs of $\phi(n, k)$ in the decreasing lexicographic order, so that we can assign an index $i$ to each motif in $\phi(n, k)$.

**Definition 3.** We denote by $p_k^i$ the $i$th motif in $\phi(n, k)$.
<table><caption>TABLE 2: $\phi(8)$.</caption><thead><tr><th>φ(n,k)</th><th>p ∈ φ(n,k)</th><th>Σ(p)</th></tr></thead><tbody><tr><td>φ(8,1)</td><td>(8)</td><td>8</td></tr><tr><td rowspan="4">φ(8,2)</td><td>(7,1)</td><td>9</td></tr><tr><td>(6,2)</td><td>10</td></tr><tr><td>(5,3)</td><td>11</td></tr><tr><td>(4,4)</td><td>12</td></tr><tr><td rowspan="4">φ(8,3)</td><td>(6,1,1)</td><td>11</td></tr><tr><td>(5,2,1)</td><td>12</td></tr><tr><td>(4,3,1)</td><td>13</td></tr><tr><td>(4,2,2)</td><td>14</td></tr><tr><td rowspan="4">φ(8,4)</td><td>(3,3,2)</td><td>15</td></tr><tr><td>(5,1,1,1)</td><td>14</td></tr><tr><td>(4,2,1,1)</td><td>15</td></tr><tr><td>(3,3,1,1)</td><td>16</td></tr><tr><td rowspan="4">φ(8,5)</td><td>(3,2,2,1)</td><td>17</td></tr><tr><td>(2,2,2,2)</td><td>20</td></tr><tr><td>(4,1,1,1,1)</td><td>18</td></tr><tr><td>(3,2,1,1,1)</td><td>19</td></tr><tr><td rowspan="2">φ(8,6)</td><td>(2,2,2,1,1)</td><td>21</td></tr><tr><td>(3,1,1,1,1,1)</td><td>23</td></tr><tr><td>φ(8,7)</td><td>(2,1,1,1,1,1,1)</td><td>29</td></tr><tr><td>φ(8,8)</td><td>(1,1,1,1,1,1,1,1)</td><td>36</td></tr></tbody></table>

The first motif $p_k^1$ in $\phi(n, k)$ is

$$ (n - k + 1, \overbrace{1, 1, \dots, 1}^{k-1 \text{ times}}) $$

and the last motif in $\phi(n, k)$ is

$$ (\overbrace{\lfloor \frac{n}{k} \rfloor, \dots, \lfloor \frac{n}{k} \rfloor, \dots, \lfloor \frac{n}{k} \rfloor}^{n \text{ mod } k \text{ times}}, \overbrace{\lfloor \frac{n}{k} \rfloor, \dots, \lfloor \frac{n}{k} \rfloor, \dots, \lfloor \frac{n}{k} \rfloor}^{k - n \text{ mod } k \text{ times}}) $$

Algorithm 1 works as follows. Given two positive integers $n$ and $k$ such that $k \le n$, and a motif $p$ under construction that is initially empty, the algorithm generates all partitions of $n$ into $k$ integers in the decreasing lexicographic order. Each partition begins by the first integer that should be between $sup$ that is $n-k+1$ if $p$ is empty, $min(n-k+1, min(p))$ otherwise, and $\lfloor \frac{n}{k} \rfloor$, the other integers being generated by a recursive call of the algorithm. Note that the first integer should not be bigger than the minimum integer in $p$ if $p$ is not empty. The integers of each partition are appended to the end of $p$ to form a complete motif in decreasing order.

For example, in the call `MOTIF(3, 8, ∅, ∅)` ($p=\phi=\emptyset$), the algorithm generates each first integer between 6 and 3. When the first integer is 6, the algorithm calls `MOTIF(2, 2, {6}, ∅)` which generates only one partition of 2 into 2 integers (i.e. `(1, 1)`)) appended into `{6}` to form a complete motif (6, 1, 1). When the first integer is 4, the algorithm calls `MOTIF(4, 2, {4}, {(6, 1, 1), (5, 3, 2)})` that generates two partitions of 4 into 2 integers : `(3, 1)` and `(2, 2)`, each partition being appended into `{4}` to form a complete motif. See Table 2 for all results.
**Algorithm 1 :** MOTIF(n, k, p, φ)

**Input** : two positive integers *n* and *k* such that *k* ≤ *n*, motif *p* under construction, set of motifs *φ* under construction

**Output** : a set of motifs *φ* in decreasing lexicographic order

1 **begin**
2 &nbsp;&nbsp;&nbsp;&nbsp;**if** *k* = 1 **then**
3 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**L** *φ* ← *φ* ∪ {*p* ∪ {*n*}};
4 &nbsp;&nbsp;&nbsp;&nbsp;**else**
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** *p* = ∅ **then**
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**L** sup ← *n* − *k* + 1;
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else**
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**L** sup ← min(*n* − *k* + 1, min(*p*));
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**inf** ← ⌊ *n* / *k* ⌋;
10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**foreach** *x* ← sup downto inf **do**
11 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**L** Motif(*n* − *x*, *k* − 1, *p* ∪ {*x*}, *φ*) ;

3.2. Principle of the new upper bounds

Given a valid coloring *X* of a graph *G* and its associated motif *p*, we will find the number *k*<sub>*t*</sub> of colors
such that all motifs with *k*<sub>*t*</sub> or more colors are dominated by *p*. Namely :

$$
\forall q \in \psi = \bigcup_{x=k_t}^{n} \phi(n, x), p \geq q \quad (3)
$$

Note that $\psi$ is not empty, because it contains trivially the only motif (1, 1, ..., 1) in $\phi(n, n)$ for $k_t = n$.
Since $\psi$ does not contain any valid coloring better than $p$, $k_t$ is an upper bound of $s(G)$. The problem is
to make $k_t$ as small as possible.

Based on this above principle, we will establish two upper bounds for s(G) : UB<sub>a</sub>, an algebraic upper bound, and UB<sub>s</sub>, an algorithmic upper bound based on a maximum stable set of G.

3.3. UB<sub>a</sub>, an algebraic upper bound for s(G)

UB<sub>a</sub> is based on the following two properties.

**Property 5.** Let $G = (V, E)$ with $|V|=n$, and $k \le n$ be an integer. The motif $p_k^1 = (n-k+1, 1, 1, \dots, 1)$ dominates all other motifs in $\phi(n, k)$.

In fact, let $q \in \phi(n, k)$. Then $\forall t$ such that $1 \le t \le k$, $\sum_{x=t+1}^{k} p_k^1[x] \le \sum_{x=t+1}^{k} q[x]$, because $p_k^1[x] = 1 \le q[x]$ when $x > 1$. So, $\sum_{x=1}^{t} p_k^1[x] = n - \sum_{x=t+1}^{k} p_k^1[x] \ge n - \sum_{x=t+1}^{k} q[x] = \sum_{x=1}^{t} q[x]$.

**Property 6.** Let $G = (V, E)$ with $|V| = n$, and $k$ and $k'$ be two integers such that $1 \le k < k' \le n$. The motif $p_k^1 = (n-k+1, 1, 1, \dots, 1)$ dominates $p_{k'}^1 = (n-k'+1, 1, 1, \dots, 1)$.

In fact, since $n - k + 1 > n - k' + 1$, $\forall t$ such that $1 \le t \le k$, $\sum_{x=1}^{t} p_k^1[x] \ge \sum_{x=1}^{t} p_{k'}^1[x]$.
Property 5 and Property 6 mean that the motif $p_k^1=(n-k+1, 1, 1, ..., 1)$ dominates any motif in $\phi(n, k')$ such that $k \le k'$. The sum coloring of $p_k^1$ is:

$$ \Sigma(p_k^1) = (n-k+1) + \sum_{x=2}^{k} x = \frac{1}{2}k^2 - \frac{1}{2}k + n \quad (4) $$

So $UB_a$ is the smallest number $\max(k-1, |X|)$ of colors such that

$$ \Sigma(p_k^1) \ge \Sigma(X) \quad (5) $$

Equation 5 means that a sum coloring with $k$ or more colors cannot be better than the known valid coloring $X$ according to Property 5 and Property 6. So, the optimal solution must be with at most $k-1$ colors if $X$ uses fewer than $k$ colors, $k$ otherwise.

Using Equation 4, Equation 5 is transformed to

$$ \frac{1}{2}k^2 - \frac{1}{2}k + n - \Sigma(X) \ge 0 \quad (6) $$

Equation 6 is valid if and only if:

$$ k \ge \frac{1 + \sqrt{1 + 8 \times (\Sigma(X) - n)}}{2} $$

Thus:

$$ UB_a = \max\left(\left\lfloor \frac{1 + \sqrt{1 + 8 \times (\Sigma(X) - n)}}{2} \right\rfloor - 1, |X|\right) \quad (7) $$

$UB_a$ is a new algebraic upper bound of $s(G)$. Note that apart from the valid coloring $X$, $UB_a$ does not consider any other structural information of $G$. We will show in the next subsection that we can obtain a better upper bound by taking into account more structural information of $G$.

### 3.4. $UB_s$, an algorithmic upper bound of $s(G)$

Although MaxClique, GCP and MSCP are all NP-hard problems, MaxClique is relatively easier to solve than GCP and MSCP in practice. For example, the state-of-the-art exact algorithm IncMaxClique [18] finds a maximum clique of any random graph of 200 vertices in few seconds, but no exact algorithm in our knowledge is able to find the chromatic number of a random graph of 200 vertices and density 0.5 in reasonable time (a random graph of density $d$ is generated by making each pair of vertices adjacent with probability $d$). So, we can find a maximum stable set of a graph $G$, which is a maximum clique in the complement graph $\bar{G}$, to compute an upper bound better than $UB_a$, based on Property 7.

**Property 7.** Let $\alpha(G)$ denote the cardinality of a maximum stable set of $G$. A motif in which the first integer is bigger than $\alpha(G)$ does not correspond to any valid coloring of $G$.

We show in the sequel how to derive an upper bound of $s(G)$ called $UB_s$ by restricting ourselves to all motifs in which the first integer is smaller than or equal to $\alpha(G)$. For this purpose, we define a notion called major motif which is motivated by the following observation. Given any valid major coloring $X$, it is sometimes possible to find two color classes $X_i$ and $X_j$ ($i<j$) such that a vertex of $X_j$ can be moved into $X_i$ to obtain another valid major coloring $X'$. Clearly $\Sigma(X')<\Sigma(X)$ and the motif $p'$ associated with $X'$ dominates the motif $p$ associated with $X$. The motif $p'$ is obtained by decrementing the $j^{th}$ integer of $p$ by 1 and incrementing the $i^{th}$ integer of $p$ by 1. We call this transformation of $p$ left-shifting operation.

Note that the left-shifting operation is not always possible, because one must keep the integers of the resulting motif in non-increasing order. Moreover, all integers in the resulting motif should be positive.
Given two integers $n$ and $k$, we are interested in those motifs in $\phi(n, k)$, called major motifs, that cannot be transformed into another motif in $\phi(n, k)$ by a left-shifting operation without incrementing the first integer.

**Example 5.** Consider $\phi(8, 4)$ (refer to Table 2). The major motifs are $(5,1,1,1)$, $(4,2,1,1)$, $(3,3,1,1)$ and $(2,2,2,2)$. In fact, unless the first integer is incremented, these motifs cannot be transformed into any motif in $\phi(8, 4)$ by a left-shifting operation.

Let $\lambda$ denote the first integer of a motif. We have $\lfloor \frac{n}{k} \rfloor \le \lambda \le n - k + 1$. Intuitively, a motif is major if it contains the maximum number ($\beta$) of integers equal to its first integer, $\lambda$. The remaining value of $n$ (i.e. $n - \beta \times \lambda$) should be partitioned into $k - \beta$ positive integers. So $\beta$ is the maximum integer satisfying $n - \beta \times \lambda \ge k - \beta$, or $\beta \le \frac{n-k}{\lambda-1}$ after excluding the trivial motif $(1, 1, \dots, 1)$ and assuming $\lambda > 1$. So, $\beta = \lfloor \frac{n-k}{\lambda-1} \rfloor$.

A major motif is formally defined in Definition 4.

**Definition 4.** Let $\lambda$ and $\beta$ be two integers such that $\lfloor \frac{n}{k} \rfloor \le \lambda \le n - k + 1$ and $\beta = \lfloor \frac{n-k}{\lambda-1} \rfloor$. A major motif in $\phi(n, k)$ is a motif $p_k^i$ with the following properties :

$$ \begin{cases} p_k^i[x] = \lambda, & \text{if } 1 \le x \le \beta; \\ p_k^i[x] = n - \beta \times \lambda - (k - \beta - 1), & \text{if } x = \beta + 1; \\ p_k^i[x] = 1, & \text{if } \beta + 1 < x \le k. \end{cases} $$

The interest of the major motif notion lies in the following two properties. The first one, Property 8, says that a major motif in $\phi(n, k)$ dominates all motifs $\phi(n, k)$ with the same first integer and represents the best sum coloring among these motifs.

**Property 8.** Let $p$ and $q$ be two motifs in $\phi(n, k)$ such that $p$ is major and $p[1] = q[1]$, then $p \succeq q$.

**Proof 1.** Let $\beta = \lfloor \frac{n-k}{p[1]-1} \rfloor$. Since $p$ is major, we have $p[1] = p[2] = \dots = p[\beta] = q[1] \ge q[2] \ge \dots \ge q[\beta]$. So, $\forall t$ such that $1 \le t \le \beta$, $\sum_{x=1}^{t} p[x] \ge \sum_{x=1}^{t} q[x]$.

Moreover, $\forall t$ such that $\beta + 1 \le t \le k$, we have $p[t+1] = p[t+2] = \dots = p[k] = 1 \le q[k] \le q[k-1] \le \dots \le q[t+1]$. So, $\sum_{x=1}^{t} p[x] = n - \sum_{x=t+1}^{k} p[x] \ge n - \sum_{x=t+1}^{k} q[x] = \sum_{x=1}^{t} q[x]$.

Therefore, $p \succeq q$. $\square$

Property 9 compares two major motifs in $\phi(n, k)$.

**Property 9.** Let $p$ and $q$ be two major motifs in $\phi(n, k)$. If $p[1] > q[1]$ then $p \succeq q$.

**Proof 2.** Let $\beta_p = \lfloor \frac{n-k}{p[1]-1} \rfloor$ and $\beta_q = \lfloor \frac{n-k}{q[1]-1} \rfloor$. Clearly $\beta_p \le \beta_q$. We have $p[1] = p[2] = \dots = p[\beta_p] > q[1] = q[2] = \dots = q[\beta_p]$. So, $\forall t$ such that $1 \le t \le \beta_p$, $\sum_{x=1}^{t} p[x] > \sum_{x=1}^{t} q[x]$.

Moreover, $\forall t$ such that $\beta_p + 1 \le t \le k$, we have $p[t+1] = p[t+2] = \dots = p[k] = 1 \le q[k] \le q[k-1] \dots, \le q[t+1]$, implying $\sum_{x=1}^{t} p[x] = n - \sum_{x=t+1}^{k} p[x] \ge n - \sum_{x=t+1}^{k} q[x] = \sum_{x=1}^{t} q[x]$. Therefore, $p \succeq q$. $\square$

Since motifs in $\phi(n, k)$ are in decreasing lexicographical order, Property 8 and Property 9 imply that a major motif in $\phi(n, k)$ dominates all subsequent motifs in $\phi(n, k)$, as stated in Property 10.
**Property 10.** Let $p_k^i \in \phi(n, k)$ be a major motif and $p_k^j \in \phi(n, k)$ such that $j > i$. Then $p_k^i \supseteq p_k^j$.

Observe that while a major coloring is the best sum coloring in a set of symmetric colorings, a major motif is the best motif in a set of motifs in the sense of Property 10. A direct consequence is that $\forall p_k^i \in \phi(n, k)$, $p_k^i \supseteq p_k^j$, because $p_k^1$ is major.

The following property compares the major motif $p_k^1$ to $p_k^i$, such that $k < k'$.

**Property 11.** Let $k$ and $k'$ be two integers such that $k < k'$, and $\psi = \bigcup_{x=k'}^{n} \{\phi(n, x)\}$, then $\forall q \in \psi$, $p_k^1 \supseteq q$.

**Proof 3.** According to Property 6, $p_k^1$ dominates $p_k^1$ $\forall x$ such that $k' \le x \le n$. Since $p_k^1$ dominates all motifs in $\phi(n, x)$ according to Property 10, $p_k^1$ dominates all motifs in $\psi$. $\square$

We now prove the most important property of this paper.

**Property 12.** Let $k$ and $k'$ be two integers such that $k < k'$. Let $p_k^i$ be a major motif and $\psi = \bigcup_{y=k'}^{n} \{\phi(n, y)\}$.

Then $\forall q \in \psi$ such that $q[1] \le p_k^i[1]$, $p_k^i \supseteq q$.

**Proof 4.** Let $\beta = \lfloor \frac{n-k}{p_k^i[1]-1} \rfloor$. Since $p_k^i$ is major, we have $p_k^i[1] = p_k^i[2] = \dots = p_k^i[\beta] \ge q[1] \ge q[2] \ge \dots \ge q[\beta]$. So, $\forall t$ such that $1 \le t \le \beta$, $\sum_{x=1}^{t} p_k^i[x] \ge \sum_{x=1}^{t} q[x]$.

Moreover, $\forall t$ such that $\beta+1 \le t \le k$, we have $p_k^i[t+1] = p_k^i[t+2] = \dots = p_k^i[k] = 1 \le q[k] \le q[k-1] \le \dots \le q[t+1]$ (q is a sequence of non-increasing positive integers), implying $\sum_{x=1}^{t} p_k^i[x] = n - \sum_{x=t+1}^{k} p_k^i[x] \ge n - \sum_{x=t+1}^{k} q[x] = \sum_{x=1}^{t} q[x]$. Therefore, $p_k^i \supseteq q$. $\square$

Given a valid coloring $X$ of a graph $G$ with $n$ vertices and the cardinality $\alpha(G)$ of a maximum stable set of $G$, we can search for the smallest $k$ and the major motif $p_k^i$ with $p_k^i[1] = \alpha(G)$ such that $\Sigma(X) < \Sigma(p_k^i)$. Property 12 says that a valid coloring of $G$ with $k$ or more colors better than $X$ cannot be found. So $UB_s = k-1$. Algorithm 2 implements $UB_s$. The function `constructMajorMotif(\lambda, k)` constructs a major motif $p \in \phi(n, k)$ such that $p[1] = \lambda$, as defined in Definition 4. The function `computeSumColoring(p)` computes the sum of color weights of $p$, as shown in Equation 1.

The complexity of the `constructMajorMotif(\lambda, k)` function and the complexity of the `computeSumColoring(p)` function are both $O(k)$. Since $k \le n$, the complexity of Algorithm 2 is $O(n^2)$.

## 4. Empirical evaluation

In this section, we compare our algebraic and algorithmic bounds ($UB_a$ and $UB_s$) for the chromatic strength of a graph $G$ with that proposed by Hajiabolhassan et al. [9] (Property 4). To find a maximum stable set of $G$, we run the state-of-the-art exact MaxClique algorithm IncMaxCLQ [18] to find a maximum clique in the complement graph $\bar{G}$. We evaluate our approach using the COLOR [12] and DIMACS [7] graphs.

Table 3 gives the experimental results. For each graph $G$, we denote by $k^*$ the best-known upper bound for the chromatic number $(\chi(G))$, $\Sigma^*$ the best-known upper bound for the chromatic sum $(\Sigma(G))$, $\alpha(G)$ the cardinality of a maximum stable set of $G$, Time$_s$ the runtime in seconds to find a maximum stable set in $G$, $UB_{hmt}$ the results of Hajiabolhassan et al. given by Property 4 using $\Delta(G)$ and $k^*$, $UB_a$ the results of our algebraic bound and $UB_s$ the results of our algorithmic bound based on a maximum stable set of $G$. Both $UB_a$ and $UB_s$ are computed using $\Sigma(G)^*$.
**Algorithm 2 :** CUB<sub>s</sub>(n, α(G), X)

**Input** : the number of vertices *n*, the cardinality of a maximum stable set α(G), and a valid coloring X

**Output** : an upper bound of *s(G)*

1 begin
2     SUM ← 0;
3     k ← |X|;      /*initialize k */
4     λ ← α(G);
5     while SUM ≤ Σ(X) do
6         k ← k + 1;
7         if n − k + 1 < λ then
8             λ ← n − k + 1;
9         p ← constructMajorMotif(λ, k);
10        SUM ← computeSumColoring(p);
11    return k − 1;
end

<table><thead><tr><th>Graph</th><th>|V|</th><th>|E|</th><th>k*</th><th>Σ*</th><th>Δ(G)</th><th>α(G)</th><th>Time<sub>s</sub></th><th>UB<sub>hmt</sub></th><th>UB<sub>a</sub></th><th>UB<sub>s</sub></th></tr></thead><tbody><tr><td>anna</td><td>138</td><td>493</td><td>11</td><td>276</td><td>71</td><td>80</td><td>0</td><td>41</td><td>17</td><td>14</td></tr><tr><td>david</td><td>87</td><td>406</td><td>11</td><td>237</td><td>82</td><td>36</td><td>0</td><td>47</td><td>17</td><td>15</td></tr><tr><td>DSJC1000.1</td><td>1000</td><td>49629</td><td>21</td><td>9931</td><td>127</td><td>N/A</td><td>N/A</td><td>74</td><td>134</td><td>N/A</td></tr><tr><td>DSJC1000.5</td><td>1000</td><td>249826</td><td>87</td><td>41603</td><td>551</td><td>15</td><td>408</td><td>319</td><td>285</td><td>187</td></tr><tr><td>DSJC1000.9</td><td>1000</td><td>449449</td><td>224</td><td>106452</td><td>924</td><td>6</td><td>223</td><td>574</td><td>459</td><td>360</td></tr><tr><td>DSJC125.1</td><td>125</td><td>736</td><td>5</td><td>326</td><td>23</td><td>34</td><td>0</td><td>14</td><td>20</td><td>11</td></tr><tr><td>DSJC125.5</td><td>125</td><td>3891</td><td>17</td><td>1012</td><td>75</td><td>10</td><td>0</td><td>46</td><td>42</td><td>29</td></tr><tr><td>DSJC125.9</td><td>125</td><td>6961</td><td>44</td><td>2503</td><td>120</td><td>4</td><td>0</td><td>82</td><td>69</td><td>58</td></tr><tr><td>DSJC250.1</td><td>250</td><td>3218</td><td>8</td><td>996</td><td>38</td><td>44</td><td>117</td><td>23</td><td>39</td><td>23</td></tr><tr><td>DSJC250.5</td><td>250</td><td>15668</td><td>28</td><td>3306</td><td>147</td><td>12</td><td>0</td><td>88</td><td>78</td><td>53</td></tr><tr><td>DSJC250.9</td><td>250</td><td>27897</td><td>72</td><td>8288</td><td>234</td><td>5</td><td>24</td><td>153</td><td>127</td><td>105</td></tr><tr><td>DSJC500.1</td><td>500</td><td>12458</td><td>12</td><td>2997</td><td>68</td><td>N/A</td><td>N/A</td><td>40</td><td>71</td><td>N/A</td></tr><tr><td>DSJC500.5</td><td>500</td><td>62624</td><td>48</td><td>11759</td><td>286</td><td>13</td><td>16</td><td>167</td><td>150</td><td>97</td></tr><tr><td>DSJC500.9</td><td>500</td><td>112437</td><td>126</td><td>30313</td><td>471</td><td>5</td><td>84</td><td>299</td><td>244</td><td>190</td></tr><tr><td>flat1000-50-0</td><td>1000</td><td>245000</td><td>50</td><td>39315</td><td>520</td><td>20</td><td>263</td><td>285</td><td>277</td><td>212</td></tr><tr><td>flat1000-60-0</td><td>1000</td><td>245830</td><td>60</td><td>40648</td><td>524</td><td>17</td><td>296</td><td>292</td><td>282</td><td>200</td></tr><tr><td>flat1000-76-0</td><td>1000</td><td>246708</td><td>76</td><td>41199</td><td>532</td><td>15</td><td>466</td><td>304</td><td>284</td><td>183</td></tr><tr><td>flat300-20-0</td><td>300</td><td>21375</td><td>20</td><td>3150</td><td>160</td><td>15</td><td>0</td><td>90</td><td>76</td><td>20</td></tr><tr><td>flat300-26-0</td><td>300</td><td>21633</td><td>26</td><td>3966</td><td>158</td><td>12</td><td>0</td><td>92</td><td>86</td><td>36</td></tr><tr><td>flat300-28-0</td><td>300</td><td>21695</td><td>28</td><td>4330</td><td>162</td><td>12</td><td>0</td><td>95</td><td>90</td><td>53</td></tr><tr><td>fpsol2.i.1</td><td>496</td><td>11654</td><td>65</td><td>3403</td><td>252</td><td>307</td><td>0</td><td>159</td><td>76</td><td>75</td></tr><tr><td>fpsol2.i.2</td><td>451</td><td>8691</td><td>30</td><td>1668</td><td>346</td><td>261</td><td>0</td><td>188</td><td>49</td><td>46</td></tr><tr><td>fpsol2.i.3</td><td>425</td><td>8688</td><td>30</td><td>1636</td><td>346</td><td>238</td><td>0</td><td>188</td><td>49</td><td>46</td></tr><tr><td>games120</td><td>120</td><td>638</td><td>9</td><td>443</td><td>13</td><td>22</td><td>0</td><td>11</td><td>25</td><td>15</td></tr><tr><td>huck</td><td>74</td><td>301</td><td>11</td><td>243</td><td>53</td><td>27</td><td>0</td><td>32</td><td>18</td><td>16</td></tr><tr><td>inithx.i.1</td><td>864</td><td>18707</td><td>54</td><td>3676</td><td>502</td><td>566</td><td>0</td><td>278</td><td>75</td><td>72</td></tr><tr><td>inithx.i.2</td><td>645</td><td>13979</td><td>31</td><td>2050</td><td>541</td><td>365</td><td>0</td><td>286</td><td>53</td><td>48</td></tr><tr><td>inithx.i.3</td><td>621</td><td>13969</td><td>31</td><td>1986</td><td>542</td><td>360</td><td>0</td><td>287</td><td>52</td><td>48</td></tr><tr><td>jean</td><td>80</td><td>254</td><td>10</td><td>217</td><td>36</td><td>38</td><td>0</td><td>23</td><td>17</td><td>15</td></tr><tr><td>le450-15a</td><td>450</td><td>8168</td><td>15</td><td>2740</td><td>99</td><td>75</td><td>45</td><td>57</td><td>68</td><td>53</td></tr></tbody></table>

Continued on next page...
<table><caption>TABLE 3: Comparison of our new algebraic bound (UB<sub>a</sub>) and algorithmic bound (UB<sub>s</sub>) with the bound of Hajia-bolhassan et al. [9] (UB<sub>hmt</sub>).</caption><thead><tr><th>Graph</th><th>|V|</th><th>|E|</th><th>k*</th><th>Σ*</th><th>Δ(G)</th><th>α(G)</th><th>Time<sub>s</sub></th><th>UB<sub>hmt</sub></th><th>UB<sub>a</sub></th><th>UB<sub>s</sub></th></tr></thead><tbody><tr><td>le450-15b</td><td>450</td><td>8169</td><td>15</td><td>2733</td><td>94</td><td>78</td><td>7</td><td>55</td><td>68</td><td>54</td></tr><tr><td>le450-15c</td><td>450</td><td>16680</td><td>15</td><td>3829</td><td>139</td><td>41</td><td>1602</td><td>77</td><td>82</td><td>57</td></tr><tr><td>le450-15d</td><td>450</td><td>16750</td><td>15</td><td>3751</td><td>138</td><td>41</td><td>2266</td><td>77</td><td>81</td><td>56</td></tr><tr><td>le450-25a</td><td>450</td><td>8260</td><td>25</td><td>3291</td><td>128</td><td>91</td><td>0</td><td>77</td><td>75</td><td>66</td></tr><tr><td>le450-25b</td><td>450</td><td>8263</td><td>25</td><td>3492</td><td>111</td><td>78</td><td>0</td><td>68</td><td>78</td><td>68</td></tr><tr><td>le450-25c</td><td>450</td><td>17343</td><td>25</td><td>4906</td><td>179</td><td>47</td><td>24</td><td>102</td><td>94</td><td>79</td></tr><tr><td>le450-25d</td><td>450</td><td>17425</td><td>25</td><td>4953</td><td>157</td><td>43</td><td>82</td><td>91</td><td>95</td><td>78</td></tr><tr><td>le450-5a</td><td>450</td><td>5714</td><td>5</td><td>1350</td><td>42</td><td>N/A</td><td>N/A</td><td>24</td><td>42</td><td>N/A</td></tr><tr><td>le450-5b</td><td>450</td><td>5734</td><td>5</td><td>1363</td><td>42</td><td>N/A</td><td>N/A</td><td>24</td><td>43</td><td>N/A</td></tr><tr><td>le450-5c</td><td>450</td><td>9803</td><td>5</td><td>1356</td><td>66</td><td>90</td><td>2</td><td>36</td><td>43</td><td>8</td></tr><tr><td>le450-5d</td><td>450</td><td>9757</td><td>5</td><td>1350</td><td>68</td><td>90</td><td>2</td><td>37</td><td>42</td><td>5</td></tr><tr><td>miles1000</td><td>128</td><td>3216</td><td>42</td><td>1690</td><td>86</td><td>8</td><td>0</td><td>64</td><td>56</td><td>48</td></tr><tr><td>miles1500</td><td>128</td><td>5198</td><td>73</td><td>3354</td><td>106</td><td>5</td><td>0</td><td>90</td><td>80</td><td>77</td></tr><tr><td>miles250</td><td>128</td><td>387</td><td>8</td><td>325</td><td>16</td><td>44</td><td>0</td><td>12</td><td>20</td><td>14</td></tr><tr><td>miles500</td><td>128</td><td>1170</td><td>20</td><td>712</td><td>38</td><td>18</td><td>0</td><td>29</td><td>34</td><td>26</td></tr><tr><td>miles750</td><td>128</td><td>2113</td><td>31</td><td>1179</td><td>64</td><td>12</td><td>0</td><td>48</td><td>46</td><td>38</td></tr><tr><td>mulsol.2</td><td>188</td><td>3885</td><td>31</td><td>1191</td><td>156</td><td>90</td><td>0</td><td>94</td><td>45</td><td>44</td></tr><tr><td>mulsol.i.1</td><td>197</td><td>3925</td><td>49</td><td>1957</td><td>121</td><td>100</td><td>0</td><td>85</td><td>59</td><td>59</td></tr><tr><td>mulsol.i.3</td><td>184</td><td>3916</td><td>31</td><td>1187</td><td>157</td><td>86</td><td>0</td><td>94</td><td>45</td><td>44</td></tr><tr><td>mulsol.i.4</td><td>185</td><td>3946</td><td>31</td><td>1189</td><td>158</td><td>86</td><td>0</td><td>95</td><td>45</td><td>44</td></tr><tr><td>mulsol.i.5</td><td>186</td><td>3973</td><td>31</td><td>1160</td><td>159</td><td>88</td><td>0</td><td>95</td><td>44</td><td>43</td></tr><tr><td>myciel3</td><td>11</td><td>20</td><td>4</td><td>21</td><td>5</td><td>5</td><td>0</td><td>5</td><td>5</td><td>4</td></tr><tr><td>myciel4</td><td>23</td><td>71</td><td>5</td><td>45</td><td>11</td><td>11</td><td>0</td><td>8</td><td>7</td><td>6</td></tr><tr><td>myciel5</td><td>47</td><td>236</td><td>6</td><td>93</td><td>23</td><td>23</td><td>0</td><td>15</td><td>10</td><td>8</td></tr><tr><td>myciel6</td><td>95</td><td>755</td><td>7</td><td>189</td><td>47</td><td>47</td><td>0</td><td>27</td><td>14</td><td>11</td></tr><tr><td>myciel7</td><td>191</td><td>2360</td><td>8</td><td>381</td><td>95</td><td>95</td><td>0</td><td>52</td><td>20</td><td>15</td></tr><tr><td>queen10-10</td><td>100</td><td>1470</td><td>10</td><td>553</td><td>35</td><td>10</td><td>0</td><td>23</td><td>30</td><td>12</td></tr><tr><td>queen11-11</td><td>121</td><td>1980</td><td>11</td><td>730</td><td>40</td><td>11</td><td>0</td><td>26</td><td>35</td><td>13</td></tr><tr><td>queen12-12</td><td>144</td><td>2596</td><td>12</td><td>940</td><td>43</td><td>12</td><td>0</td><td>28</td><td>40</td><td>14</td></tr><tr><td>queen13-13</td><td>169</td><td>3328</td><td>13</td><td>1190</td><td>48</td><td>13</td><td>0</td><td>31</td><td>45</td><td>16</td></tr><tr><td>queen14-14</td><td>196</td><td>4186</td><td>14</td><td>1478</td><td>51</td><td>14</td><td>0</td><td>33</td><td>51</td><td>17</td></tr><tr><td>queen15-15</td><td>225</td><td>5180</td><td>15</td><td>1811</td><td>56</td><td>15</td><td>0</td><td>36</td><td>56</td><td>19</td></tr><tr><td>queen16-16</td><td>256</td><td>6320</td><td>16</td><td>2190</td><td>59</td><td>16</td><td>0</td><td>38</td><td>62</td><td>20</td></tr><tr><td>queen5-5</td><td>25</td><td>160</td><td>5</td><td>75</td><td>16</td><td>5</td><td>0</td><td>11</td><td>10</td><td>5</td></tr><tr><td>queen6-6</td><td>36</td><td>290</td><td>6</td><td>138</td><td>19</td><td>6</td><td>0</td><td>13</td><td>14</td><td>10</td></tr><tr><td>queen7-7</td><td>49</td><td>476</td><td>7</td><td>196</td><td>24</td><td>7</td><td>0</td><td>16</td><td>17</td><td>7</td></tr><tr><td>queen8-12</td><td>96</td><td>1368</td><td>12</td><td>624</td><td>32</td><td>8</td><td>0</td><td>22</td><td>33</td><td>12</td></tr><tr><td>queen8-8</td><td>64</td><td>728</td><td>9</td><td>291</td><td>27</td><td>8</td><td>0</td><td>18</td><td>21</td><td>10</td></tr><tr><td>queen9-9</td><td>81</td><td>1056</td><td>10</td><td>409</td><td>32</td><td>9</td><td>0</td><td>21</td><td>26</td><td>11</td></tr><tr><td>school1</td><td>385</td><td>19095</td><td>14</td><td>2674</td><td>282</td><td>41</td><td>2</td><td>148</td><td>68</td><td>45</td></tr><tr><td>school1-nsh</td><td>352</td><td>14612</td><td>14</td><td>2392</td><td>232</td><td>39</td><td>0</td><td>123</td><td>64</td><td>43</td></tr><tr><td>zeroein.i.1</td><td>211</td><td>4100</td><td>49</td><td>1822</td><td>111</td><td>120</td><td>0</td><td>80</td><td>57</td><td>56</td></tr><tr><td>zeroein.i.2</td><td>211</td><td>3541</td><td>30</td><td>1004</td><td>140</td><td>127</td><td>0</td><td>85</td><td>40</td><td>39</td></tr><tr><td>zeroein.i.3</td><td>206</td><td>3540</td><td>30</td><td>998</td><td>140</td><td>123</td><td>0</td><td>85</td><td>40</td><td>39</td></tr></tbody></table>

The results in Table 3 shows that our algebraic bound (UB<sub>a</sub>) is already better than the results of Hajiabolhassan et al. given by Property 4 (UB<sub>hmt</sub>), except for some graphs with low degree (le450, queen). UB<sub>a</sub> gives a better lower bound for 42 instances among 74. However, when a maximum stable set can be found in reasonable time using IncMaxCLQ, our algorithmic bound (UB<sub>s</sub>) is significantly better than UB<sub>hmt</sub> in general. UB<sub>s</sub> gives a better
lower bound for 66 instances among 74. For example, while $UB_{hmt}$ for the three graphs *inithx* is 278, 286 and 287 respectively, $UB_s$ is 72, 48 and 48 respectively ($UB_a$ is 75, 53 and 52 respectively). Another example is the graph *le450-5d* for which $UB_{hmt} = 37$, while $UB_s = 5$. These results show the performance of our approach for reducing the number of colors to be considered when solving *MSCP*.

## 5. Conclusion

In this paper we focused on one component of the Minimum Sum Coloring Problem (*MSCP*), the chromatic strength *s*(*G*) of the graph *G*. We have proposed two new upper bounds of *s*(*G*), called $UB_a$ and $UB_s$ respectively. $UB_a$ and $UB_s$ both use a known valid coloring *X* of the graph and explore a set of motifs representing an abstraction of all possible colorings of the graph. $UB_a$ is obtained by identifying the number of colors from which a coloring better than *X* cannot be obtained.

Apart from *X*, $UB_a$ does not exploit any other structure property of the graph. $UB_s$ is a more established upper bound. In order to determine $UB_s$, we introduced a notion called major motif that exploits the dominance relation on the set of motifs. Indeed, such a motif represents the best sum coloring among all motifs with the same or more number of colors and the same or smaller first integer.

Computing $UB_s$ consists in identifying a major motif whose the first integer is the cardinality of a maximum stable set of the graph, and whose the sum coloring is greater than the sum of *X*. The maximum stable set is computed using the exact MaxClique algorithm IncMaxCLQ. Thus, we exclude the colorings that cannot be valid for the graph and the colorings that cannot be better than *X*. $UB_s$ is derived from the remaining colorings thanks to our algorithm $CUB_s$.

We evaluated $UB_a$ and $UB_s$ on DIMACS and COLOR graphs. The experimental results show that $UB_a$ is already better than the previous bounds except for some graphs with low degree. The algorithmic upper bound $UB_s$, based on the major motif notion and a maximum stable set, outperforms generally all others bounds allowing to reduce substantially the search space when solving *MSCP*.

In the future, we plan to integrate more structural properties of a graph to further improve $UB_s$, and to develop efficient algorithms to solve *MSCP* based on $UB_s$.

*Acknowledgements.* This work is supported by the Ministry of Higher Education and Research, of the French state.

## 6. References

[1] Amotz Bar-Noy, Mihir Bellare, Magnús M Halldórsson, Hadas Shachnai, and Tami Tamir. On chromatic sums and distributed resource allocation. *Information and Computation*, 140(2):183-202, 1998.

[2] Amotz Bar-Noy and Guy Kortsarz. Minimum color sum of bipartite graphs. *Journal of Algorithms*, 28(2):339-365, 1998.

[3] Una Benlic and Jin-Kao Hao. A study of breakout local search for the minimum sum coloring problem. In *Simulated Evolution and Learning*, pages 128-137. Springer, 2012.

[4] Flavia Bonomo and Mario Valencia-Pabon. Minimum sum coloring of $p$ 4-sparse graphs. *Electronic Notes in Discrete Mathematics*, 35:293-298, 2009.

[5] Flavia Bonomo and Mario Valencia-Pabon. On the minimum sum coloring of $p$ 4-sparse graphs. *Graphs and Combinatorics*, 30(2):303-314, 2014.

[6] Daniel Brélaz. New methods to color the vertices of a graph. *Communications of the ACM*, 22(4):251-256, 1979.

[7] ftp://dimacs.rutgers.edu/pub/challenge/graph/benchmarks/color/.

[8] Michael R Garey and David S Johnson. A guide to the theory of np-completeness. *WH Freemann, New York*, 1979.
[9] Hossein Hajiabolhassan, Mojtaba L Mehrabadi, and Ruzbeh Tusserkani. Minimal coloring and strength of graphs. *Discrete Mathematics*, 215(1):265-270, 2000.

[10] Godfrey H Hardy and Srinivasa Ramanujan. Asymptotic formulaæ in combinatory analysis. *Proceedings of the London Mathematical Society*, 2(1):75-115, 1918.

[11] Alain Hertz, Matthieu Plumettaz, and Nicolas Zufferey. Variable space search for graph coloring. *Discrete Applied Mathematics*, 156(13):2551-2560, 2008.

[12] http://mat.gsia.cmu.edu/COLOR/instances.html.

[13] Klaus Jansen. The optimum cost chromatic partition problem. In *Algorithms and complexity*, pages 25–36. Springer, 1997.

[14] Klaus Jansen. Approximation results for the optimum cost chromatic partition problem. *Journal of Algorithms*, 34(1):54–89, 2000.

[15] Yan Jin, Jin-Kao Hao, and Jean-Philippe Hamiez. A memetic algorithm for the minimum sum coloring problem. *Computers & Operations Research*, 43:318–327, 2014.

[16] Ewa Kubicka and Allen J Schwenk. An introduction to chromatic sums. In *Proceedings of the 17th conference on ACM Annual Computer Science Conference*, pages 39–45. ACM, 1989.

[17] Clément Lecat, Chu-Min Li, Corinne Lucet, and Yu Li. Exact methods for the minimum sum coloring problem. In *Doctoral Program of Constraint Programming (CD-DP’15)*, pages 61–69, 2015.

[18] Chu-Min Li, Zhiwen Fang, and Ke Xu. Combining maxsat reasoning and incremental upper bound for the maximum clique problem. In *Tools with Artificial Intelligence (ICTAI), 2013 IEEE 25th International Conference on*, pages 939–946. IEEE, 2013.

[19] Yu Li, Corinne Lucet, Aziz Moukrim, and Kaoutar Sghiouer. Greedy algorithms for the minimum sum coloring problem. In *Logistique et transports*, pages LT-027, 2009.

[20] Zhipeng Lü and Jin-Kao Hao. A memetic algorithm for graph coloring. *European Journal of Operational Research*, 203(1):241–250, 2010.

[21] Corinne Lucet, Florence Mendes, and Aziz Moukrim. An exact method for graph coloring. *Computers & operations research*, 33(8):2189–2207, 2006.

[22] Michal Malafiejski. *Sum coloring of graphs*, chapter 4, pages 55–66. Graph Coloring. 2004.

[23] Isabel Méndez-Díaz and Paula Zabala. A branch-and-cut algorithm for graph coloring. *Discrete Applied Mathematics*, 154(5):826-847, 2006.

[24] John Mitchem and Patrick Morriss. On the cost-chromatic number of graphs. *Discrete Mathematics*, 171(1):201-211, 1997.

[25] Aziz Moukrim, Kaoutar Sghiouer, Corinne Lucet, and Yu Li. Lower bounds for the minimal sum coloring problem. *Electronic Notes in Discrete Mathematics*, 36:663-670, 2010.

[26] Daniel Cosmin Porumbel, Jin-Kao Hao, and Pascale Kuntz. A search space àIJcartographyâI for guiding graph coloring heuristics. *Computers & Operations Research*, 37(4):769-778, 2010.

[27] Mohammad R Salavatipour. On sum coloring of graphs. *Discrete Applied Mathematics*, 127(3):477-488, 2003.

[28] Kaoutar Sghiouer, Li Yu, Corinne Lucet, and Aziz Moukrim. A memetic algorithm for the minimum sum coloring problem. In *Conférence Internationale en Recherche Opérationnelle (CIRO’2010)*, 2010.

[29] Carsten Thomassen, Paul Erdös, Yousef Alavi, Paresh J Malde, and Allen J Schwenk. Tight bounds on the chromatic sum of a connected graph. *Journal of Graph Theory*, 13(3):353-357, 1989.

[30] Zhaoyang Zhou, Chu-Min Li, Chong Huang, and Ruchu Xu. An exact algorithm with learning for the graph coloring problem. *Computers & Operations Research*, 51:282-301, 2014.