Teorema de Hajós para Coloração Ponderada - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2007

Teorema de Hajós para Coloração Ponderada

Résumé

A coloração ótima dos vértices de um grafo é um dos problemas mais estudados em teoria dos grafos devido ao número de aplicações que o problema modela e à dificuldade inerente ao problema, pois determinar o número cromático de um grafo é NP-difícil. O Teorema de Hajós clássico [Hajós, 1961] mostra uma condição necessária e suficiente para que um grafo possua número cromático pelo menos k: o grafo deve possuir um subgrafo k-construtíıvel. Este, por sua vez, é obtido a partir do grafo completo de ordem k pela aplicação de um conjunto de operações bem determinadas. Neste artigo, provamos que a coloração ponderada [Guan and Zhu, 1997] admite também uma versão do Teorema de Hajós e, portanto, apresentamos uma condição necessária e suficiente para que o número cromático ponderado de um grafo seja pelo menos k, um inteiro qualquer.
Fichier principal
Vignette du fichier
Teorema_de_Hajos_para_Ponderada.pdf (219.62 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00533376 , version 1 (05-11-2010)

Identifiants

  • HAL Id : inria-00533376 , version 1

Citer

Julio Araujo, Claudia Linhares Sales. Teorema de Hajós para Coloração Ponderada. XXXIX Simpósio Brasileiro de Pesquisa Operacional, SBPO 2007., Aug 2007, Fortaleza, Brazil. pp.2631-2635. ⟨inria-00533376⟩
193 Consultations
47 Téléchargements

Partager

Gmail Facebook X LinkedIn More