Coloración de gráficos orientados

La coloración de gráficos dirigidos es un tipo especial de coloración de gráficos . Es decir, es la asignación de colores a los vértices de un grafo dirigido [1] , que

Otra definición: Una coloración k orientada de un dígrafo H es un homomorfismo orientado a un dígrafo k -vértice H* [2] .

Número cromático orientado

El número cromático orientado de un dígrafo G es el número mínimo de colores necesarios en una coloración orientada. Este número generalmente se denota como . La misma definición se puede extender a gráficos no dirigidos definiendo el número cromático dirigido de un gráfico no dirigido como el número cromático máximo de todas sus orientaciones [3] [2] .

Ejemplos

El número cromático orientado de un ciclo orientado de 5 vértices es cinco. Si el ciclo está coloreado con cuatro o menos colores, entonces dos vértices adyacentes tendrán el mismo color o dos vértices a través de uno tendrán el mismo color. En el último caso, los bordes que conectan estos dos vértices con el vértice en el medio se colorearán incorrectamente (segunda regla): ambos arcos tienen los mismos extremos de color, pero conectan los colores en la dirección opuesta. Por lo tanto, no es posible colorear con cuatro o menos colores. Si coloreamos todos los vértices de diferentes colores, obtenemos una coloración orientada admisible.

Propiedades

Una coloración orientada solo puede existir para dígrafos sin bucles y sin 2 ciclos orientados, ya que un bucle da un color en ambos extremos de un arco, y la segunda regla no permite 2 ciclos: dos colores están conectados en direcciones opuestas . Si se cumplen estas condiciones, siempre hay un coloreado orientado, por ejemplo, si asignamos colores diferentes a todos los vértices.

Si una coloración orientada es completa , en el sentido de que no se pueden fusionar dos colores en el mismo color para dar una coloración adecuada, entonces la coloración corresponde a un homomorfismo de un solo torneo . El torneo tiene un vértice para cada color en el colorido. Para cada par de colores, hay un arco en el gráfico de colores con estos dos colores en los extremos, que corresponde a la orientación del borde en el torneo entre los vértices de los colores correspondientes. Las coloraciones incompletas también se pueden representar mediante un homomorfismo de torneo, pero en este caso la correspondencia entre coloraciones y homomorfismos no es uno a uno.

Los gráficos no dirigidos con género acotado, grado acotado o número cromático acíclico acotado también tienen un número cromático dirigido acotado [3] .

Estimaciones para el número cromático orientado

El número cromático orientado de un gráfico puede diferir significativamente de su número cromático (ordinario). Por ejemplo, hay gráficos bipartitos con un número cromático orientado arbitrariamente grande, es suficiente reemplazar cada borde del gráfico con un camino de longitud 2, y luego los extremos de cada uno de esos caminos en el gráfico resultante deben pintarse en diferentes colores. [4] .

Courcelle [5] probó que para cualquier gráfico plano, y Raspud y Soupina [6] mejoraron el resultado a 80. Borodin y otros publicaron el siguiente teorema [7] :

Teorema : Sea G una gráfica plana de g , entonces
(1) (2) (3) (4)


En otro artículo de Borodin [8] , la restricción en (1) del teorema se relajó a 13.

Notas

  1. ↑ En el artículo, un grafo dirigido significa un grafo dirigido. En la versión en inglés del libro de Distel "Graph Theory", los gráficos orientados son gráficos dirigidos sin bucles o bordes múltiples, es decir, los gráficos dirigidos son gráficos dirigidos sin bucles y bordes múltiples, mientras que en la traducción rusa del libro, los gráficos dirigidos son gráficos dirigidos. gráficos sin bucles y múltiples aristas. Esto conduce a frecuentes confusiones.
  2. ↑ 1 2 BORODÍN, IVANOVA, 2005 , p. 239.
  3. ↑ 1 2 Kostochka, Sopena, Zhu, 1997 , p. 331–340.
  4. ↑ BORODÍN, IVANOVA, 2005 , p. 240.
  5. ↑ Courselle, 1994 .
  6. ↑ Raspaud, Sopena, 1994 , págs. 171-174.
  7. ↑ Borodin, Kostochka, Nešetřil, Raspaud, Sopena, 1999 , págs. 77-90.
  8. ↑ Borodin, Kim, Kostochka, West, 2004 , págs. 147-159.

Literatura