inria-00533376, version 1
Teorema de Hajós para Coloração Ponderada
Julio Araujo 1Claudia Linhares Sales
a, 1, 2
XXXIX Simpósio Brasileiro de Pesquisa Operacional, SBPO 2007. (2007) 2631-2635
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.
- a – Universidade Federal do Ceará
- 1 : Parallelism, Graphs and Optimization Research Group (ParGO)
- Universidade Federal do Ceara
- 2 : MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
- INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
- Domaine : Informatique/Mathématique discrète
- inria-00533376, version 1
- http://hal.inria.fr/inria-00533376
- oai:hal.inria.fr:inria-00533376
- Contributeur : Julio Araujo
- Soumis le : Vendredi 5 Novembre 2010, 18:30:46
- Dernière modification le : Vendredi 10 Décembre 2010, 12:07:25