Item request has been placed! ×
Item request cannot be made. ×
loading  Processing Request

Teorema de Hajós para Coloração Ponderada

Item request has been placed! ×
Item request cannot be made. ×
loading   Processing Request
اقرأ أكثر حفظ في قائمتي
  • معلومة اضافية
    • Contributors:
      Parallelism, Graphs and Optimization Research Group (ParGO); Universidade Federal do Ceará = Federal University of Ceará (UFC); Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE); Inria Sophia Antipolis - Méditerranée (CRISAM); Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED); Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S); Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S); Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)
    • بيانات النشر:
      HAL CCSD
    • الموضوع:
      2007
    • Collection:
      HAL Université Côte d'Azur
    • الموضوع:
      Fortaleza; Brazil
    • نبذة مختصرة :
      International audience ; 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.
    • Relation:
      inria-00533376; https://inria.hal.science/inria-00533376; https://inria.hal.science/inria-00533376/document; https://inria.hal.science/inria-00533376/file/Teorema_de_Hajos_para_Ponderada.pdf
    • الدخول الالكتروني :
      https://inria.hal.science/inria-00533376
      https://inria.hal.science/inria-00533376/document
      https://inria.hal.science/inria-00533376/file/Teorema_de_Hajos_para_Ponderada.pdf
    • Rights:
      info:eu-repo/semantics/OpenAccess
    • الرقم المعرف:
      edsbas.4CF66A6D