Teorema de Hajós para Coloração Ponderada

Julio Araujo 1 Claudia Linhares Sales 1, 2
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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.
Type de document :
Communication dans un congrès
XXXIX Simpósio Brasileiro de Pesquisa Operacional, SBPO 2007., Aug 2007, Fortaleza, Brazil. pp.2631-2635, 2007, Anais do Simpósio
Liste complète des métadonnées

Littérature citée [6 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00533376
Contributeur : Julio Araujo <>
Soumis le : vendredi 5 novembre 2010 - 18:30:46
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : dimanche 6 février 2011 - 03:03:26

Fichier

Teorema_de_Hajos_para_Ponderad...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00533376, version 1

Collections

Citation

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, 2007, Anais do Simpósio. 〈inria-00533376〉

Partager

Métriques

Consultations de la notice

276

Téléchargements de fichiers

74