J Araujo
email: julio.araujo@inria.fr

C Linhares Sales

A Hajós-like Theorem for Weighted Coloring

 shows a necessary and sufficient condition for the chromatic number of a given graph G be at least k: G must contain a kconstructible subgraph. A graph is k-constructible if it can be obtained from a complete graph of order k by successively applying a set of well-defined operations.

Given a vertex-weighted graph G and a (proper) rcoloring c = {C 1 , . . . , C r } of G, the weight of a color class C i is the maximum weight of a vertex colored i and the weight of c is the sum of the weights of its color classes. The objective of the Weighted Coloring Problem [7] is, given a vertex-weighted graph G, to determine the minimum weight of a proper coloring of G, that is its weighted chromatic number.

In this article, we prove that the Weighted Coloring Problem admits a version of the Hajós' Theorem and so we show a necessary and sufficient condition for the weighted chromatic number of a vertex-weighted graph G be at least k, for any positive real k.

Introduction

For the terms not defined here the reader can be referred to [START_REF] Bondy | Graph Theory[END_REF].

Given a graph G = (V, E), a k-coloring c of G is an assignment of colors to the vertices of G, c : V (G) → {1, . . . , k}, such that if (u, v) ∈ E, then c(u) = c(v). The chromatic number of a graph G, χ(G), is the smallest integer k such that G admits a k-coloring.

The Vertex Coloring Problem consists in, for a given a graph G, determining χ(G). It is a well known fact that it is a NP-hard problem [START_REF] Karp | Reducibility among combinatorial problems[END_REF].

The characterization of the k-chromatic graphs, i.e., graphs G such that χ(G) = k, has been a challenging problem for many years. In 1961, Hajós [START_REF] Hajós | Über eine konstruktion nicht n-färbbarer graphen[END_REF] gave a characterization of graphs with chromatic number at least k by proving that they must contain a k-constructible subgraph. In order to present this characterization, we need to recall some definitions. The identification of two vertices a and b of a graph G means the removal of a and b followed by the inclusion of a new vertex a • b adjacent to each vertex in N G (a) ∪ N G (b), where N G (x) is the set of neighbors of a vertex x in a graph G. A graph G = (V, E) is complete if it is simple and for every pair of vertices u, v of G, uv ∈ E(G). We denote by K n the complete graph with n vertices.

Definition 1

The set of k-constructible graphs is defined recursively as follows:

1. The complete graph on k vertices is k-constructible. Theorem 11 (Hajós [8])

χ(G) ≥ k if and only if G is a supergraph of a k-constructible graph.
The Hajós' Theorem determines a set of operations that we can use to obtain, from a complete graph with k vertices, all k-chromatic graphs, including the k-critical ones. A graph H is k-critical if χ(H) ≥ k and for every proper subgraph I of H, χ(I) < k. Clearly, for a given graph G, the difficulty of determining whether χ(G) ≥ k is equivalent to the difficulty of determining if G contains a k-critical subgraph H. Thanks to the Hajós' Theorem, we know that all the k-critical graphs can be built from complete graphs on k vertices by successive applications of Hajós Sum and Identification of vertices. Because of this, it has been subject of interest to obtain Hajós-like Theorem for several variations of the classical coloring problem. Gravier [START_REF] Gravier | A hajós-like theorem for list coloring[END_REF] proved an extension of Hajós' Theorem for List Coloring. Král [START_REF] Kral | Hajós' theorem for list coloring[END_REF] gave a simplified proof of Gravier's result. Zhu [17] found an extension of this theorem for chromatic circular number. Mohar [START_REF] Mohar | Hajós' theorem for colorings of edge-weighted graphs[END_REF] demonstrated two new versions of the referred theorem for chromatic circular number and an extension of Hajós' Theorem for the channel assignment problem, i.e., a coloring of edge-weighted graphs.

In this paper, we are interested in a variation of the classical Vertex Coloring Problem, which is called the Weighted Coloring Problem. In order to present it, we need some definitions.

Given a simple graph G = (V, E), an assignment w of non-negative real weights to its vertices and a proper k-coloring c = {C 1 , . . . , C k } of G, the weight of a color class C i in the coloring c is the maximum weight of a vertex in this color class. Moreover, the weight of a kcoloring c, denoted by w(c), is the sum of the weights of its color classes.

The Weighted Coloring Problem [START_REF] Guan | A coloring problem for weighted graphs[END_REF] consists in, for a given graph G with non-negatives real weights associated to its vertices, determining the minimum weight of a proper coloring of G, that is, the weighted chromatic number of G, denoted by χ w (G):

χ w (G) = min c coloring of G w(c)
When all the vertices of the input graph G have equal weights, the Weighted Coloring Problem is equivalent to the Vertex Coloring Problem. Then, the former is particular case of the second one. Consequently, Weighted Coloring is also N P -Hard.

The complexity of this problem was already studied in some previous works. It was shown that the weighted chromatic number of a graph G can be calculated in polynomial-time whenever G is a bipartite graph with only two different weights associated to its vertices [START_REF] Demange | Weighted node coloring: When stable sets are expensive[END_REF], or G is a P 5 -free bipartite graph [START_REF] De Werra | Weighted coloring on planar, bipartite and split graphs: Complexity and improved approximation[END_REF], or G belongs to a subclass of P 4 -sparse graphs that properly contains the cographs [START_REF] Araujo | Weighted coloring on p 4 -sparse graphs[END_REF].

On the other hand, it was proved that the decision version of Weighted Coloring is N P -complete for bipartite graphs [START_REF] Demange | Weighted node coloring: When stable sets are expensive[END_REF], split graphs [START_REF] Demange | Weighted node coloring: When stable sets are expensive[END_REF], planar graphs [START_REF] De Werra | Weighted coloring on planar, bipartite and split graphs: Complexity and improved approximation[END_REF], interval graphs [START_REF] Escoffier | Weighted coloring: futher complexity and approximability results[END_REF] and others graph classes.

In the next section, we show an extension of Hajós' Theorem for Weighted Coloring.

Hajós' Theorem for Weighted Coloring

In this section, we deal with simple (vertex-)weighted graphs. We denote by G = (V, E, w) a vertex-weighted graph G = (V, E) together with its function weight w :

V → R + .
Notation 21 The infinity family of complete weighted graphs G = (V, E, w) with order n = |V (G)| and such that v∈V w(v) = k is denoted by K k n .

Notation 22 Given a weighted graph G = (V, E, w) and a proper coloring c of G, we choose as the representative of the color i in c, rep c (i), a unique vertex v ∈ V satisfying the inequality w(v) ≥ w(x), for all

x ∈ V such that c(x) = c(v) = i. Definition 2 Given weighted graphs G = (V, E, w) and H = (V ′ , E ′ , w ′ ), we say that H ⊆ G (H is a weighted subgraph of G) if V ′ ⊆ V , E ′ ⊆ E, and, for all v ∈ V ′ , we have w ′ (v) ≤ w(v).
Now, we redefine the Hajós' construction to the weighted case: Definition 3 The weighted k-constructible graphs are defined recursively as follows:

1. The graphs in i∈N K k i are weighted k-constructible. The main result of this paper is:

Theorem 21 Let G = (V, E, w) be a weighted graph and k be a positive real. Therefore, χ w (G) ≥ k if and only if G has a weighted k-constructible weighted subgraph H.

Proof In order to simplify the notation, whenever we refer to subgraph in this proof, we mean weighted subgraph, as in Definition 2. We prove first that if χ w (G) ≥ k, then G has a weighted k-constructible subgraph H. Suppose, by contradiction, that this statement is false and consider as counter-example a graph G = (V, E, w) which is maximal with respect to its number of edges. It means that χ w (G) ≥ k and G does not contain any weighted kconstructible subgraph and for any pair of non-adjacent vertices of G, let us say u, v, G ′ = G + uv contains a weighted k-constructible subgraph.

We claim that G is not isomorphic to a complete multipartite graph. Suppose the contrary and let p be the number of stable sets in the partition P of V (G). For each color class C i of an optimal weighted coloring c of G, there is no pair of vertices of C i in distinct sets of P, since there is an edge between any two vertices of distinct parts.

Moreover, we cannot have more than one color class in one stable set. As a matter of fact, suppose by contradiction that there are two color classes, say C i and C j , whose vertices belong to the same stable set in the partition P of V (G). Without loss of generality, suppose that w(rep c (i)) ≥ w(rep c (j)). Then a coloring c ′ , obtained from c by the union of the color classes C i and C j , has cost exactly χ w (G) -w(rep c (j)), and this contradicts the optimality of c.

Consequently, the vertices with the greatest weight in every part are exactly the representatives of each color class. Observe that the subgraph induced by the representatives is an element of the set K k p , because χ w (G) ≥ k and p ∈ N. This contradicts the hypothesis that G has no weighted k-constructible subgraph.

Therefore, the counter-example G is not a complete multipartite graph. Thus, there are at least three vertices in G, let us say a, b and c, such that ab, bc / ∈ E(G) and ac ∈ E(G). Consider now the graphs G 1 = G + ab and G 2 = G + bc. Because of the maximality of G, G 1 and G 2 have, respectively, weighted k-constructible subgraphs H 1 and H 2 . Obviously, the edges ab and bc belong, respectively, to H 1 and H 2 . Consider then the application of Hajós Sum in two disjoint graphs isomorphic to H 1 and H 2 , respectively. Let us choose edge ab of H 1 and bc of H 2 to remove and let us identify the vertices labeled b. Finally, identify all the vertices in H 1 with their correspondent vertices in H 2 , if they exist. Observe that a graph isomorphic to a subgraph of G is obtained at the end of this sequence of operations. Then, G has a weighted k-constructible subgraph, a contradiction.

Conversely, we prove now that, if G has a weighted k-constructible subgraph H, then χ w (G) ≥ k. First, observe that χ w (G) ≥ χ w (H). Then, we just have to show that χ w (H) ≥ k. The proof is by induction on the number of Hajós' operations applied to obtain H.

If H is isomorphic to a graph K k i ∈ K k i , for some i ∈ N, then its weighted chromatic number is trivially k, since it is a complete graph whose sum of weights is equal to k.

Suppose then that H was obtained by the Weighted Identification of two non-adjacent vertices a and b of a weighted k-constructible graph H ′ into a vertex a • b. By induction hypothesis, H ′ has a weighted chromatic number at least k. Suppose, by contradiction, that χ w (H) < k and let c be an optimal weighted coloring of H. Then, a coloring c ′ of H ′ can be obtained from c, by assigning to a and b the color assigned to a • b in c, and letting all the other vertices of H ′ be assigned to the same color they have been assigned in c. Observe that, except the color i of a•b, for all the other colors j, rep c ′ (j) = rep c (j). For the color i, the vertex rep c (i) has weight greater than or equal to the weight of a • b, that is greater than or equal to the weight of a and b. Therefore, the coloring c ′ has weight equal to the coloring c, that is less than k. This contradicts the hypothesis of χ w (H ′ ) ≥ k.

Finally, suppose that H was obtained from weighted k-constructible graphs H 1 and H 2 using the Weighted Hajós' Sum on the edges (a 1 , b 1 ) and (a 2 , b 2 ) from H 1 and H 2 , respectively. Let a 1 • a 2 be the vertex of H obtained by the identification of a 1 e a 2 . Suppose, by contradiction, that χ(H) < k, while χ(H 1 ) ≥ k and χ(H 2 ) ≥ k. Consider an optimal weighted coloring c of H. Observe that either c(a 1 • a 2 ) = c(b 1 ) or c(a 1 • a 2 ) = c(b 2 ) (because b 1 and b 2 are adjacent). Without loss of generality, suppose that c(a 1 • a 2 ) = c(b 1 ). Then, consider now the restriction c ′ of c to H 1 , assigning to a 1 the color of a 1 • a 2 . We have that, for all color class C j of c ′ , the weight of rep c ′ (j) ≤ rep c (j) (including the color class of a 1 , because the weight of a 1 is less than or equal to the weight of a 1 • a 2 ). Consequently, w(c ′ ) ≤ w(c) < k, contradicting the hypothesis that χ w (H 1 ) ≥ k.

Conclusions

Ore [START_REF] Ore | The four color problem[END_REF] has proved that the Hajós construction can be simplified. He has shown that by using only one operation that collapses the two Hajós operations, one may construct any k-colorable graph from complete graphs of order k.

It is not difficult to see that the same simplification can be done for the weighted case. It is just necessary use the same adaptation we did whenever two vertices u and v are identified, i.e., the weight of the new vertex must be the maximum value between the weight of u and the weight of v.

Moreover, by extending the ideas of Urquhart [START_REF] Urquhart | The graph constructions of hajós and ore[END_REF] for the non-weighted case, it is also not hard to establish the equivalence between the class of the weighted kconstructible graphs and the class obtained by using the adapted Ore's operation described above.

Finally, there is a well known problem that is to study the complexity of the construction of k-chromatic graphs of a given size by Hajós operations [START_REF] Hanson | Remarks on the graph colour theorem of hajós[END_REF][START_REF] Jensen | Graph Coloring Problems[END_REF][START_REF] Mansfield | Some colouring problems and their complexity[END_REF]. Since the Vertex Coloring Problem is a particular case of Weighted Coloring, it is obvious that the complexity of this problem in the weighted case is as hard as in the non-weighted one and can also be let as open question.

2 .

 2 Hajós' Sum: If G 1 and G 2 are disjoint graphs which are k-constructible, (a 1 , b 1 ) is an edge of G 1 and (a 2 , b 2 ) is an edge of G 2 , then the graph G obtained from G 1 ∪ G 2 by removing (a 1 , b 1 ) and (a 2 , b 2 ), identifying a 1 with a 2 , and adding an edge between (b 1 , b 2 ), is a k-constructible graph (see Figure 2).

Fig. 1

 1 Fig. 1 Hajós' Sum.

3 .

 3 Identification: If G is k-constructible and a and b are two non-adjacent vertices of G, then the graph obtained by the identification of a and b is a kconstructible graph.

2 .

 2 Weighted Hajós' Sum: If G 1 and G 2 are disjoint weighted k-constructible graphs, (a 1 , b 1 ) is an edge of G 1 and (a 2 , b 2 ) is an edge of G 2 , then the graph G obtained from G 1 ∪ G 2 by removing (a 1 , b 1 ) and (a 2 , b 2 ), identifying a 1 with a 2 into a vertex a 1 • a 2 , doing w(a 1 • a 2 ) = max {w(a 1 ), w(a 2 )}, and adding the edge (b 1 , b 2 ) is a weighted k-constructible graph. 3. Weighted Identification: If a and b are two nonadjacent vertices of a weighted k-constructible G, then the graph that we obtain by the identification of two vertices a and b into a vertex a•b, doing w(a• b) = max{w(a), w(b)}, is a weighted k-constructible graph.

Partially supported by CNPq/Brazil (Conselho Nacional de Desenvolvimento Científico e Tecnológico), FUNCAP/Brazil (Fundação Cearense de Apoio ao Desenvolvimento Científico e Tecnológico) and INRIA/France (Institut Nationale de Recherche en Informatique et Automatique), project numbers INR-0046-00014.01.00/11, PRN-0040-00040.01.00/10 and CNPq 202049/2012-4. BP 93 -F06902 Sophia-Antipolis