HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Friday, November 5, 2010 - 6:30:46 PM
Last modification on : Friday, February 4, 2022 - 3:11:42 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

190

Files downloads

42