Un gráfico coloreable único

Un gráfico coloreable de forma única es un gráfico de k colores que admite solo una (correcta) k -coloración (hasta la permutación de colores).

Ejemplos

Un gráfico completo se puede colorear de forma única porque solo hay un color válido: a cada vértice se le asigna un color diferente.

Cualquier árbol k es únicamente coloreable con ( k  + 1) colores. Los gráficos planos que se pueden colorear únicamente con 4 colores son exactamente gráficos de Apolonio , es decir, 3 árboles planos [1] .

Propiedades

Algunas propiedades de un gráfico G únicamente k coloreable con n vértices y m aristas:

  1. metro ≥ ( k - 1) norte - k ( k -1)/2 [2] [3]

Conceptos relacionados

Mínima imperfección

Un gráfico mínimamente imperfecto es un gráfico en el que cada subgráfico es perfecto . La eliminación de cualquier vértice de un gráfico mínimamente imperfecto deja un subgráfico coloreable de forma única.

Coloración de borde de un solo valor

Un gráfico de línea coloreable de forma única es un gráfico de k - borde - coloreado que admite solo un color (correcto) de k - borde - hasta una permutación de colores . Solo los caminos y los ciclos admiten una coloración de 2 aristas de un solo valor. Para cualquier valor de k , las estrellas K 1, k son únicamente gráficos coloreables de k -bordes . Sin embargo, Wilson [4] planteó una conjetura y Thomason [5] probó que para k ≥ 4 estos son los únicos miembros de esta familia. Hay, sin embargo, gráficos únicamente coloreables de 3 aristas que no entran en esta clasificación, como el gráfico de pirámide triangular .

Si un gráfico cúbico se puede colorear únicamente en 3 aristas, debe tener exactamente tres ciclos hamiltonianos formados por aristas de dos (de tres) colores, pero algunos gráficos cúbicos con solo tres ciclos hamiltonianos no tienen una coloración única en 3 aristas. [6] . Cualquier gráfico cúbico plano simple que admita una coloración única de 3 aristas contiene un triángulo [1] , pero Tut [7] notó que el gráfico de Petersen generalizado G (9,2) es un gráfico libre de triángulos no planos , pero es Únicamente 3-edge-colorable. Durante muchos años, este gráfico fue el único ejemplo de este tipo de gráficos (véanse los artículos de Bolobash [8] y Schwenk [9] ), pero ahora hay un número infinito de gráficos cúbicos sin triángulos no planos que tienen un solo valor de 3 aristas. -colorear [6] .

Coloración completa uno a uno

Un único gráfico totalmente coloreable es un gráfico totalmente k -coloreado que admite solo una (correcta) k -coloración total (hasta la permutación de colores).

Los gráficos vacíos , los caminos y los ciclos con una longitud divisible por 3 son gráficos únicos totalmente coloreables. Mahmudian y Shokrollahi [10] conjeturaron que solo estos gráficos forman la familia.

Algunas propiedades de un grafo G totalmente k -coloreable de forma única con n vértices:

  1. χ″( G ) = Δ( G ) + 1 a menos que G = K 2 [11]
  2. Δ( GRAMO ) ≤ 2 δ( GRAMO ). [once]
  3. Δ( G ) ≤ n/2 + 1. [12]

Aquí χ″( G ) es el número cromático total ; Δ( G ) es el grado máximo y δ( G ) es el grado mínimo.

Notas

  1. ↑ 12 Cazador de aves , 1998 .
  2. ↑ Truszczynski, 1984 .
  3. ↑ Xu, 1990 .
  4. ↑ Wilson, 1976 .
  5. ↑ Thomason, 1978 .
  6. ↑ 1 2 Belcastro, Haas, 2015 .
  7. ↑ Tutte, 1976 .
  8. ↑ Bollobas, 1978 .
  9. ↑ Schwenk, 1989 .
  10. ↑ Mahmoodian, Shokrollahi, 1995 .
  11. ↑ 1 2 Akbari, Behzad, Hajiabolhassan, Mahmoodian, 1997 .
  12. ↑ Akbari, 2003 .

Literatura

Enlaces