Coloración libre de conflictos
Este artículo es huérfano , ya que ningún otro artículo lo enlaza . Introduzca enlaces a esta página desde artículos relacionados ; pruebe la herramienta Buscar enlaces para obtener sugerencias. ( Junio de 2024 ) |
La coloración libre de conflictos es una generalización de la noción de coloración de gráficos a los hipergráficos . [1]
Definición
Un hipergrafo H tiene un conjunto de vértices V y un conjunto de aristas E. Cada arista es un subconjunto de vértices (en un grafo, cada arista contiene como máximo dos vértices, pero en un hipergrafo puede contener más de dos).
Una coloración es una asignación de un color a cada vértice de V.
Una coloración no presenta conflictos si al menos un vértice de cada arista tiene un color único. Si H es un grafo, esta condición se convierte en la condición estándar para una coloración legal de un grafo: los dos vértices adyacentes a cada arista deben tener colores diferentes.
Aplicaciones
Las coloraciones libres de conflictos surgen en el contexto de la asignación de bandas de frecuencia a antenas celulares , en aspectos de consumo de batería de redes de sensores y en protocolos RFID . [1]
Casos especiales
Un caso especial común es cuando los vértices son puntos en el plano y las aristas son subconjuntos de puntos contenidos en el mismo disco . En este contexto, una coloración de los puntos se denomina libre de conflictos si, para cada disco cerrado D que contiene al menos un punto del conjunto, hay un color que aparece precisamente una vez. Cualquier coloración libre de conflictos de cada conjunto de n puntos en el plano utiliza al menos c log n colores, para una constante absoluta c > 0. Lo mismo es cierto no solo para los discos sino también para las copias homotéticas de cualquier cuerpo convexo . [2]
Otro caso especial es cuando los vértices son vértices de un grafo, y las aristas son conjuntos de vecinos. En este contexto, una coloración de los vértices se llama libre de conflictos si, para cada vértice v , hay un color que se asigna exactamente a un vértice entre v y sus vecinos. En este contexto, la variante libre de conflictos de la Conjetura de Hadwiger se cumple: Si un grafo G no contiene K k +1 como menor , entonces tiene una coloración libre de conflictos con como máximo k colores. Para grafos planares , a veces son necesarios tres colores y siempre son suficientes para una coloración libre de conflictos. Es NP-completo decidir si un grafo planar tiene una coloración libre de conflictos con un color, y si un grafo planar tiene una coloración libre de conflictos con dos colores. [3]
Enlaces externos
- Colorear sin conflictos (Shakhar Smorodinsky) en YouTube
Referencias
- ^ ab Smorodinsky, Shakhar (2013), Bárány, Imre; Böröczky, Károly J.; Tóth, Gábor Fejes; Pach, János (eds.), "Coloración sin conflictos y sus aplicaciones", Geometría: intuitiva, discreta y convexa: un tributo a László Fejes Tóth , Estudios matemáticos de la Sociedad Bolyai, vol. 24, Berlín, Heidelberg: Springer, págs. 331–389, arXiv : 1005.3616 , doi : 10.1007/978-3-642-41498-5_12, ISBN 978-3-642-41498-5, S2CID 174683 , consultado el 20 de enero de 2021
- ^ Pach, János; Tóth, Géza (2003), Aronov, Boris; Basu, Saugata; Pach, János; Sharir, Micha (eds.), "Colores sin conflictos", Geometría discreta y computacional: The Goodman-Pollack Festschrift , Algoritmos y combinatoria, vol. 25, Berlín, Heidelberg: Springer, págs. 665–671, doi :10.1007/978-3-642-55566-4_30, ISBN 978-3-642-55566-4, consultado el 20 de enero de 2021
- ^ Abel, Zachary; Alvarez, Victor; Demaine, Erik D.; Fekete, Sándor P.; Gour, Aman; Hesterberg, Adam; Keldenich, Phillip; Scheffer, Christian (1 de enero de 2018). "Coloración de grafos sin conflictos". Revista SIAM de Matemáticas Discretas . 32 (4): 2675–2702. doi :10.1137/17M1146579. hdl : 1721.1/122951 . ISSN 0895-4801.
 | Este artículo relacionado con la teoría de grafos es un esbozo . Puedes ayudar a Wikipedia expandiéndolo. |
