info.info-dm
Julio Araujo 
  
Claudia Linhares Sales 
  
Claudia Linhares 
email: linhares@lia.ufc.br
  
Sales Teorema De Hajós 
  
Júlio César 
email: juliocesar@lia.ufc.br
  
Silva Araújo 
  
Cláudia Linhares Sales 
  
Palavras Chave 
  
Coloração De Grafos 
  
  
  
  
  
  
  
  
  
  
Teorema de Hajós para Coloração Ponderada

Keywords: Graph coloring, Hajós' Theorem, Weighted Coloring AREA: Graph Theory

à 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.

Introdução

O problema de coloração de grafos consiste em determinar qual é o número cromático de um grafo G, χ(G), i.e., a menor quantidade de cores tal que G admite uma coloração própria, na qual vértices adjacentes devem receber cores diferentes.

Um problema que generaliza o problema de coloração de grafos, definido por Guan e Zhu [START_REF] Guan | A coloring problem for weighted graphs[END_REF], é o problema de coloração de grafos com vértices ponderados, o qual chamamos coloração ponderada. Neste, dado um grafo G com pesos associados aos vértices, deseja-se encontrar o número cromático ponderado de G, χ p (G).

Seja w c (i) o maior peso de um vértice em G, colorido com a cor i, por uma coloração c. Então, encontrar χ p (G) consiste em determinar o menor valor de ∀i w c (i), para toda coloração c própria de G.

Claramente, o problema de coloração de grafos é em coloração de ponderada, o caso onde todos os vértices têm peso unitário.

Hajós [Hajós, 1961] provou que χ(G) ≥ k se, e somente se, G é supergrafo de um grafo k-construtível. O conjunto dos grafos k-construtíveis é definido recursivamente como segue:

1. O grafo completo com k vértices é k-construtível.
2. Se G é k-construtível e x e y são dois vértices não-adjacentes de G, então o grafo obtido pela identificação de x e y e a remoção de arestas múltiplas, caso elas existam, também será k-construtível.

3. Se G 1 e G 2 são grafos k-construtíveis disjuntos, (a 1 , b 1 ) é aresta de G 1 e (a 2 , b 2 ) é aresta de G 2 , então o grafo G obtido a partir de G 1 ∪ G 2 pela remoção das arestas (a 1 , b 1 ) e (a 2 , b 2 ), identificação de a 1 com a 2 e adição da aresta (b 1 , b 2 ), também será k-construtível.
O Teorema de Hajós determina um conjunto de operações que permitem, a partir de um grafo completo com k vértices, obter todos os grafos k-cromáticos, inclusive os kcríticos. Um subgrafo k-crítico H de um grafo G é um subgrafo de G tal que χ(H) ≥ k e é minimal com relação a esta propriedade, i.e., para todo subgrafo próprio I de H, χ(I) < k. Similarmente, no caso de coloração ponderada, chamamos um subgrafo kcrítico H de um grafo ponderado G, um grafo tal que χ p (H) ≥ k e é minimal com relação a esta propriedade. Em outras palavras, dado um grafo G (ponderado), a dificuldade em determinar se χ(G) ≥ k (analogamente, χ p (H) ≥ k), é equivalente à dificuldade de determinar os subgrafos k-críticos de G. O Teorema de Hajós nos fornece exatamente um meio para construí-los.

Existem resultados na literatura sobre extensões do Teorema de Hajós para diferentes tipos de coloração. Gravier [Gravier, 1996] provou uma extensão do Teorema de Hajós para coloração por listas. Kral [Kral, 2004] forneceu uma prova simplificada do resultado de Gravier. Zhu [Zhu, 2003] encontrou uma extensão deste teorema para o número cromático circular. Mohar [Mohar, 2005] demonstrou duas novas versãos do referido teorema para o número cromático circular e uma extensão do Teorema de Hajós para o problema de atribuição de canais, i.e., uma coloração de grafos ponderados em arestas. Neste artigo, apresentaremos uma extensão do Teorema de Hajós para coloração ponderada.

Definições

Definição 2.1 Dado um grafo G = (V, E), uma coloração própria de G é uma função c : V -→ Z, tal que se (x, y) ∈ E, então c(x) = c(y). Definição 2.2 Dado um grafo G = (V, E), uma função de pesos nos vértices w : V -→ R ≥1 e uma coloração própria c de G, chamamos de representante da cor i em c, rep c (i), um e somente um, v ∈ V tal que w(v) ≥ w(x), ∀x ∈ V , onde c(x) = c(v) = i.
Definição 2.3 Dados os grafos G = (V, E), H = (V , E ) e duas funções de pesos nos vértices w :

V -→ R ≥1 e w : V -→ R ≥1 , dizemos que H ⊆ G (H é subgrafo de G) se V ⊆ V , E ⊆ E e ∀v ∈ V ∩ V temos w (v) ≤ w(v). Notação 2.1 Denotamos o conjunto de grafos G = (V, E), ponderados por funções w, completos de ordem y, tal que v∈V (G) w(v) = x, por K x y .
Dado um grafo G = (V, E), ponderado por uma função w : V -→ R ≥1 , determinar o número cromático ponderado de G, χ p (G), consiste em determinar: Prova: Provemos primeiro que se χ p (G) ≥ k, então G possui um subgrafo H k-construtível. Suponhamos, por absurdo, que o teorema é falso e consideremos um grafo G ponderado, contra-exemplo maximal em arestas. Vamos provar primeiro que G não é um grafo multipartite completo. Suponhamos, por absurdo, o contrário, e seja p a quantidade de partições de G. Há dois casos a examinar:

χ p (G) = min    v∈V (G) w(v) | v = rep c (i), ∀c coloração própria de G, i ∈ Z    3
1. p ≥ k: Nesse caso, G contém um subgrafo isomorfo ao K k k . Basta, em k partições, escolhermos um vértice de cada. Mas, isso contradiz a escolha de G como contraexemplo. 

G 1 = G + (a, b) e G 2 = G + (b, c). Pela maximalidade de G, G 1 e G 2 possuem, respectivamente, subgrafos
H 1 e H 2 que são grafos k-construtíveis. Obviamente, as arestas (a, b) e (b, c) pertencem, respectivamente, a H 1 e H 2 , pois foi a inclusão dessas arestas que gerou um subgrafo kconstrutível em G 1 e G 2 . Agora, consideremos a aplicação da Soma de Hajós em H 1 e H 2 nas arestas (a, b) de H 1 e (b, c) de H 2 , identificando os vértices rotulados b. Por último, identifiquemos todos os vértices de H 1 com os seus vértices correspondentes em H 2 , caso eles existam. Observemos que um grafo isomorfo a um subgrafo de G é obtido ao final dessa seqüência de identificações. Logo, G contém um subgrafo k-construtível. Absurdo.

Vamos provar agora que, se G possui um subgrafo H k-construtível, então χ p (G) ≥ k. Observemos que χ p (G) ≥ χ p (H). Logo, basta mostrar que χ p (H) ≥ k. Demonstremos por indução no número de operações de Hajós (definidas em 3.1) aplicadas para se obter H.

Suponhamos que H é isomorfo a um dos grafos básicos K k i , ∀i ∈ {1, . . . , k}. Nesse caso, em qualquer coloração de H, cada classe de cor contém um único vértice de H e, portanto, o número cromático ponderado de H é igual a k.

Se H não é um grafo k-construtível básico, H foi obtido por uma das operações definidas em 3.1.

Suponhamos que H tenha sido obtido através da identificação de dois vértices nãoadjacentes a e b de um grafo H k-construtível. Seja ab o vértice de H obtido pela identificação de a e b. Por hipótese de indução, H possui número cromático ponderado pelo menos k. Suponhamos, por absurdo, que χ p (H) < k e consideremos uma coloração ponderada ótima c de H. Logo, uma coloração c de H pode ser obtida a partir de c, atribuindo-se a a e b a cor de ab e mantendo-se as cores dos outros vértices tais como lhes foram atribuídas por c. Observemos que, exceto pela cor i de ab, para todas as outras cores j, rep c (j) = rep c (j). Para a cor i, o rep c (i) tem peso superior ou igual ao peso de ab, que, por sua vez, é superior ou igual ao peso de a e b. Portanto, a coloração c tem peso igual ao da coloração c que é inferior a k, contradizendo a hipótese de H ser k-construtível.

Finalmente, Suponhamos agora que H foi obtido a partir de grafos k-construtíveis H 1 e H 2 pela Soma de Hajós nas arestas (a 1 , b 1 ) e (a 2 , b 2 ) de H 1 e H 2 , respectivamente. Seja a 1 a 2 o vértice de H obtido pela identificação a 1 e a 2 . Suponhamos, por absurdo, que χ(H) < k, enquanto χ(H 1 ) ≥ k e χ(H 2 ) ≥ k. Consideremos uma coloração ponderada ótima c de H. Observemos que c(a 1 a 2 ) = c(b 1 ) ou c(a 1 a 2 ) = c(b 2 ) (pois b 1 e b 2 são adjacentes). Sem perda de generalidade, suponhamos que c(a 1 a 2 ) = c(b 1 ). Logo, uma coloração c obtida pela restrição de c a H 1 , atribuindo-se a a 1 a cor de a 1 a 2 é tal que para toda classe de cor j de c , temos que o peso de rep c (j) ≤ rep c (j) (inclusive para a cor j de a 1 , pois o peso de a 1 é inferior ou igual ao peso de a 1 a 2 ). Conseqüentemente, o peso de c é inferior ou igual ao peso de c, que, por sua vez, é inferior a k, contradizendo a hipótese de H 1 ser k-construtível.

  Teorema de Hajós para Coloração Ponderada Considere a variação da construção de Hajós definida a seguir: Definição 3.1 O conjunto dos grafos k-construtíveis é redefinido recursivamente como segue: 1. Os grafos K k i , ∀i ∈ {1, . . . , k} são k-construtíveis. 2. Dado um grafo G = (V, E) k-construtível, o grafo H = (V , E ), obtido pela identificação de dois vértices não-adjacentes de G, a e b, e remoção de eventuais arestas múltiplas, gerando um vértice ab em V , onde w(ab) = max{w(a), w(b)}, também será k-construtível. 3. Soma de Hajós: Dados dois grafos disjuntos G 1 e G 2 e duas arestas (a 1 , b 1 ) e (a 2 , b 2 ), pertencendo respectivamente a G 1 e G 2 , o grafo G obtido a partir de G 1 ∪ G 2 pela remoção de (a 1 , b 1 ) e (a 2 , b 2 ), identificação de a 1 com a 2 , gerando um vértice a 1 a 2 , onde w(a 1 a 2 ) = max {w(a 1 ), w(a 2 )} e adicionando uma aresta entre b 1 e b 2 , também será k-construtível. Teorema 3.1 Seja G = (V, E) um grafo ponderado. Então, χ p (G) ≥ k se, e somente se, G possui um subgrafo H, tal que H é k-construtível.

  2. p < k: Observemos que, em cada classe de cor da coloração ótima c, não há quaisquer dois vértices em partições distintas de G. Mais ainda, não pode existir mais de uma classe de cor em uma mesma partição. Por absurdo, suponhamos que existem duas classes de cores (cores i e j), cujos vértices pertencem a uma única partição de G. Consideremos os vértices x e y como sendo rep c (i) e rep c (j), respectivamente. Suponhamos que w(x) ≥ w(y), então uma coloração c , obtida a partir de c pela união das classes de cores i e j, tem custo exatamente χ p (G) -w(y), contradizendo a otimalidade de c. Logo, cada partição é totalmente colorida por uma mesma classe de cor. Dessa forma, os vértices com maior peso em cada partição serão exatamente os representantes de cada classe de cor. Por conseguinte, observemos que o subgrafo induzido pelos representantes contém um elemento do conjunto K k p , visto que χ p (G) ≥ k e p < k. Isto é um absudo, pois não existia subgrafo k-construtível em G. Logo, G não é multipartite completo. Conseqüentemente, G não satisfaz à relação de equivalência de não-adjacência. Então, existem três vértices em G, digamos a, b e c, tais que (a, b), (b, c) / ∈ E(G) e (a, c) ∈ E(G). Consideremos agora os grafos