Skip to Main content Skip to Navigation
Conference papers

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 , Laboratoire I3S - 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download

https://hal.inria.fr/inria-00533376
Contributor : Julio Araujo <>
Submitted on : Friday, November 5, 2010 - 6:30:46 PM
Last modification on : Monday, October 12, 2020 - 10:30:18 AM
Long-term archiving on: : Sunday, February 6, 2011 - 3:03:26 AM

File

Teorema_de_Hajos_para_Ponderad...
Files produced by the author(s)

Identifiers

  • 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. ⟨inria-00533376⟩

Share

Metrics

Record views

349

Files downloads

108