Número de jueves

El número de Thue  es una característica de un gráfico, una variante especial del índice cromático . Definido como el número mínimo de colores necesarios para una coloración no repetitiva , es decir, asignar colores a los bordes de un gráfico de manera que no haya una ruta simple de longitud uniforme en el gráfico en la que los colores de los bordes en la primera mitad del camino forman la misma secuencia que los colores de los bordes en la segunda mitad del viaje.

Introducido en 2002 por un grupo de matemáticos dirigido por Noga Alon [1] , recibió su nombre de Axel Thue , quien estudió las palabras libres cuadradas necesarias para definir rigurosamente un número.

Las variaciones de esta función también se han estudiado mediante la coloración de vértices y, de manera más general, las rutas [2] [3] [4] [5] .

Ejemplo

Considere un pentágono , es decir, un ciclo con cinco vértices. Si coloreamos los bordes con dos colores, algunos de los dos bordes adyacentes tendrán el mismo color . El camino formado por estos dos bordes tendrá una secuencia repetitiva de colores . Si pinta los bordes con tres colores, uno de los tres colores se usará solo una vez. El camino de cuatro aristas formado por los otros dos colores tendrá aristas consecutivas con el mismo color o formará una secuencia repetitiva . Con cuatro colores, no es difícil evitar la repetición, por lo que el número Thue del ciclo es cuatro.

Resultados

Alon y otros utilizaron el lema local de Lovas para demostrar que el número de Thue de cualquier gráfico es como máximo el cuadrado de su grado máximo. Dieron un ejemplo que muestra que para algunos gráficos esta dependencia cuadrática es necesaria. Además, demostraron que el número de Thue de un camino de cuatro o más vértices es exactamente tres, el número de Thue de cualquier ciclo es como mucho cuatro y el número de Thue de un grafo de Petersen es exactamente cinco.

Los ciclos conocidos con Thue número cuatro son , , ', , , . Alon et al conjeturaron que el número Thue de cualquier ciclo más grande es tres. Por medio de la verificación computacional, se aseguraron de que los ciclos enumerados anteriormente son los únicos con Thue número cuatro entre los ciclos de duración . En 2002, se demostró que todos los ciclos de 18 o más de longitud tienen un número Thue de 3 [6] .

Complejidad computacional

Comprobar si una coloración tiene una ruta repetitiva es NP-completo , por lo que comprobar si una coloración no se repite está contenida en la clase co-NP , y Fedor Manin demostró que es co-NP-completa . El problema de encontrar tal coloración pertenece a la jerarquía de polinomios , y Manin también demostró que es completa para este nivel.

Notas

  1. ↑ Noga, Grischuk, Khalushchiak, Riordan, 2002 .
  2. ↑ Barat, Waryu, 2008 .
  3. ↑ Barat, Wood, 2005 .
  4. ↑ Brechard, Klavzhar, 2004 .
  5. ↑ Kündgen, Pelsmeier, 2008 .
  6. ↑ Curri, 2002 .

Literatura