Coloración de lista impar de gráficos de pequeño género de Euler sin ciclos cortos de tipos específicos

Información Básica

• ID del artículo: 2508.15255
• Título: Odd list-coloring of graphs of small Euler genus with no short cycles of specific types
• Autores: Rishi Balaji, Victoria Khazhinsky, Chun-Hung Liu, Kevin Qin
• Clasificación: math.CO (Matemática Combinatoria)
• Fecha de publicación: 14 de octubre de 2025
• Enlace del artículo: https://arxiv.org/abs/2508.15255

Resumen

Este artículo investiga la versión de coloración de lista de la coloración impar de gráficos. El resultado principal demuestra que si un gráfico G puede incrustarse en un toro o botella de Klein, no contiene ciclos de longitud 3, 4 o 6, y no tiene dos ciclos de 5 que compartan una arista, entonces para cada función que asigne a cada vértice un conjunto de colores de tamaño 5, existe una coloración apropiada tal que algún color aparece un número impar de veces en la vecindad de cada vértice no aislado. En particular, cada gráfico que puede incrustarse en un toro o botella de Klein sin ciclos de longitud 3, 4, 6 u 8 es impar 5-seleccionable. La investigación demuestra que el número de colores en estos resultados es óptimo.

Antecedentes de investigación y motivación

Definición del problema

1. Problema de coloración impar: La coloración impar es una variante de la coloración propia que requiere que para cada vértice no aislado, al menos un color aparezca un número impar de veces en su vecindad
2. Coloración de lista: Cada vértice tiene una lista de colores disponibles, y la coloración debe seleccionar colores de sus respectivas listas
3. Gráficos incrustados en superficies: Estudio de propiedades de coloración de gráficos que pueden incrustarse en superficies específicas (toro, botella de Klein)

Importancia de la investigación

• Aunque el concepto de coloración impar es relativamente nuevo (introducido en 2022 por Petruševski y Škrekovski), ha atraído amplia atención
• Combina dos conceptos importantes en teoría de gráficos: incrustación en superficies y estructura de ciclos restringida
• Tiene importancia significativa para comprender el comportamiento de la teoría de coloración de gráficos bajo restricciones topológicas

Limitaciones de investigaciones existentes

• Petruševski y Škrekovski conjeturan que todo gráfico plano es impar 5-coloreable, pero el mejor resultado actual es impar 8-coloreable
• Hay menos resultados conocidos para gráficos en superficies más generales
• La investigación de versiones de coloración de lista de coloración impar es aún más escasa

Contribuciones principales

1. Teorema principal: Demuestra que gráficos que pueden incrustarse en un toro o botella de Klein y satisfacen condiciones de ciclos específicas son impar 5-seleccionables
2. Resultados de optimalidad: Demuestra que el número de colores requerido 5 es óptimo, con contraejemplos que requieren 6 o 7 colores
3. Marco técnico: Desarrolla resultados técnicos más fuertes (versión generalizada del Teorema 1.1, Teorema 1.3)
4. Innovación metodológica: Utiliza el método de descarga (discharging method) para analizar sistemáticamente la estructura del gráfico

Explicación detallada de métodos

Definición de la tarea

Entrada: Gráfico G, incrustable en toro o botella de Klein, satisfaciendo condiciones de restricción de longitud de ciclo, y asignación 5-lista L Salida: Coloración L-apropiada tal que algún color aparece un número impar de veces en la vecindad de cada vértice no aislado Restricciones:

• Sin ciclos de longitud 3, 4 o 6
• Sin dos ciclos de 5 que compartan una arista

Métodos técnicos principales

Concepto de R-longitud

Para un gráfico G y conjunto de aristas R ⊆ E(G), la R-longitud de un ciclo C se define como |E(C)| + |E(C) ∩ R|. Este concepto unifica el tratamiento del problema original y versiones generalizadas.

Vértices R-relajados

Un vértice v es R-relajado si:

• deg(v) es impar o 0, o
• v es adyacente a alguna arista en R

Teorema técnico principal (Teorema 1.3)

Sea G incrustable en toro o botella de Klein, R ⊆ E(G). Si:

• No hay ciclos de R-longitud 3, 4 o 6
• No hay dos ciclos de R-longitud 5 que compartan exactamente una arista

entonces para cada asignación 5-lista L, existe una coloración L-apropiada tal que para cada vértice no R-relajado, algún color aparece un número impar de veces en su vecindad.

Estrategia de demostración

Análisis de contraejemplo mínimo

Asumiendo que existe un contraejemplo mínimo G, se analiza sus propiedades estructurales:

1. Conectividad: Se demuestra que G debe ser conexo (Lema 3.1)
2. Grado mínimo: Cada vértice tiene grado al menos 3 (Lema 3.2)
3. Restricción de 3-vértices: Los vértices de grado 3 no pueden ser adyacentes a demasiados vértices R-relajados (Lema 3.3)
4. Estructura de ciclos: Análisis detallado de la R-longitud de 3-ciclos, 4-ciclos, 5-ciclos y sus relaciones mutuas

Método de descarga

Utiliza la técnica clásica de descarga:

Carga inicial:

• Vértice v: ch(v) = deg(v) - 4
• Cara f: ch(f) = leng(f) - 4

Reglas de descarga (R1)-(R8):

• (R1): Cara (≥5) envía 1/2 unidades de carga a vértices adyacentes de grado 3
• (R2)-(R6): Transferencia de carga entre caras
• (R7): Vértice (≥5) envía 1/2 unidades de carga a caras adyacentes de grado 3
• (R8): Vértice (≥6) envía 1/3 unidades de carga a 5-caras que satisfacen condiciones

Análisis de carga

Mediante cálculo de carga refinado, se demuestra:

• La carga final de cada vértice y cara es no negativa
• La carga total es estrictamente positiva
• Esto contradice la fórmula de Euler, negando así la existencia del contraejemplo

Configuración experimental

Verificación teórica

Este trabajo es puramente teórico, verificando resultados principalmente mediante demostración matemática:

1. Demostración constructiva: Para gráficos que satisfacen las condiciones, se proporciona constructivamente una coloración impar 5
2. Construcción de contraejemplos: Se demuestra la optimalidad del número de colores 5
   • Un 5-ciclo no es impar 4-seleccionable
   • La 1-subdivisión de K₇ no es impar 6-seleccionable
   • La 1-subdivisión de K₆ no es impar 5-seleccionable

Herramientas técnicas

• Fórmula de Euler para restricciones de gráficos en superficies
• Aplicación sistemática del método de descarga
• Técnicas de análisis local de estructura de gráficos

Resultados experimentales

Resultados principales

Teorema 1.1 (Teorema principal)

Un gráfico G incrustable en toro o botella de Klein sin ciclos de longitud 3, 4 o 6 y sin dos ciclos de 5 que compartan una arista es impar 5-seleccionable.

Corolario 1.2

Un gráfico G incrustable en toro o botella de Klein sin ciclos de longitud 3, 4, 6 u 8 es impar 5-seleccionable.

Optimalidad

• El número de colores 5 es óptimo: un 5-ciclo requiere 5 colores
• Las restricciones de longitud de ciclo son necesarias: existen contraejemplos de cintura 6 que requieren 6-7 colores

Verificación de resultados técnicos

Se demuestra mediante análisis estructural detallado los lemas clave:

• Lema 3.5: Un 3-ciclo debe tener R-longitud 5, y todos los vértices son R-relajados
• Lema 3.16: Un 4-vértice no puede ser adyacente solo a 4-caras
• Lema 4.11: Después de la descarga, la carga total es estrictamente positiva

Trabajo relacionado

Desarrollo de investigación en coloración impar

1. Origen: Petruševski y Škrekovski (2022) introducen el concepto y conjeturan que todo gráfico plano es impar 5-coloreable
2. Resultados para gráficos planos:
   • Demostración inicial: impar 9-coloreable
   • Mejora: Petr y Portier demuestran impar 8-coloreable
3. Generalización a superficies: Metrebian así como Tian y Yin demuestran que gráficos de toro son impar 9-coloreables

Antecedentes de coloración de lista

• La coloración de lista es una rama importante de la teoría de coloración
• Este artículo es el primero en investigar sistemáticamente la versión de lista de coloración impar
• La combinación de incrustación en superficies y restricciones de estructura de ciclos es una nueva dirección de investigación

Contribuciones metodológicas

• Aplicación del método de descarga a coloración impar
• Introducción del concepto de R-longitud que unifica el tratamiento de diferentes casos
• Proporciona un marco técnico para investigación posterior

Conclusiones y discusión

Conclusiones principales

1. Bajo restricciones apropiadas de estructura de ciclos, los gráficos en toro y botella de Klein poseen buenas propiedades de coloración de lista impar
2. Cinco colores son suficientes para manejar esta clase de gráficos, y este límite es ajustado
3. El método de descarga es una herramienta efectiva para analizar este tipo de problemas

Limitaciones

1. Restricción de superficie: Los resultados se aplican solo a superficies con género de Euler como máximo 2
2. Condiciones de ciclo: Se requiere excluir múltiples ciclos cortos, las condiciones son bastante restrictivas
3. Constructividad: La demostración es de existencia, sin proporcionar algoritmos eficientes

Direcciones futuras

1. Generalización a superficies de género más alto
2. Relajación de las condiciones de restricción de longitud de ciclo
3. Investigación de complejidad algorítmica y métodos de construcción específicos
4. Exploración de propiedades de coloración de lista impar para otras clases de gráficos

Evaluación profunda

Fortalezas

Innovación técnica

1. Innovación conceptual: La introducción de conceptos de R-longitud y R-relajado unifica elegantemente diferentes variantes del problema
2. Rigor metodológico: La aplicación del método de descarga es muy sistemática y completa
3. Resultados óptimos: Se demuestra la optimalidad del número de colores, los resultados son ajustados

Contribución teórica

1. Resultados novedosos: Progreso importante en el campo de coloración de lista impar
2. Marco técnico: Proporciona métodos que pueden servir de referencia para investigación posterior
3. Completitud: Desde resultados principales hasta detalles técnicos están bien tratados

Valor académico

1. Importancia del problema: Conecta teoría de coloración de gráficos, teoría de gráficos topológicos y optimización combinatoria
2. Profundidad de resultados: Revela la influencia de restricciones de superficie en propiedades de coloración
3. Generalidad de métodos: Las técnicas pueden ser aplicables a otros problemas relacionados

Insuficiencias

Limitaciones técnicas

1. Condiciones restrictivas: Los requisitos sobre estructura de ciclos son bastante complejos, lo que puede limitar aplicaciones prácticas
2. Limitación de superficie: Solo trata los casos más simples de superficies no triviales
3. Ausencia de algoritmos: No se proporciona algoritmo específico para construir coloración impar

Profundidad de análisis

1. Dependencia de parámetros: El análisis de por qué se requieren exactamente 5 colores carece de profundidad en cuanto a razones esenciales
2. Caracterización de estructura: La caracterización de propiedades estructurales de gráficos que satisfacen las condiciones es limitada
3. Potencial de generalización: El potencial de generalización de técnicas a otros problemas requiere exploración adicional

Influencia

Influencia teórica

• Proporciona herramientas técnicas importantes y resultados para el desarrollo de la teoría de coloración impar
• Puede inspirar nuevas direcciones de investigación en teoría de coloración de gráficos en superficies
• La nueva aplicación del método de descarga puede influir en técnicas de demostración relacionadas

Valor práctico

• Aunque es resultado puramente teórico, puede tener valor potencial en aplicaciones como coloración de redes y asignación de espectro
• Proporciona base teórica para diseño de algoritmos

Reproducibilidad

• La demostración es completa y detallada, con línea técnica clara
• Los resultados principales pueden ser verificados independientemente
• Proporciona base sólida para trabajo posterior

Escenarios de aplicación

1. Investigación teórica: Investigación en teoría de coloración de gráficos, teoría de gráficos topológicos
2. Diseño de algoritmos: Problemas de redes que requieren propiedades de coloración especiales
3. Enseñanza: Como caso clásico de aplicación del método de descarga
4. Investigación de generalización: Generalización a otras clases de gráficos o variantes de coloración

Referencias

El artículo cita 38 referencias relacionadas, incluyendo principalmente:

Teoría fundamental:

• Trabajo relacionado con el Teorema de los Cuatro Colores 4,5,6,34
• Teoría de coloración de gráficos en superficies 3,18,20,22,33

Investigación en coloración impar:

• Origen del concepto 32
• Resultados para gráficos planos 31,14,11
• Generalización a superficies 29,36

Métodos técnicos:

• Aplicación del método de descarga 25
• Problemas de coloración relacionados 1,2,10,12,16,17,24,26,27

Evaluación general: Este es un artículo teórico de alta calidad que realiza una contribución importante en el campo emergente de coloración de lista impar. La técnica es rigurosa, los resultados son óptimos, y sienta una base sólida para el desarrollo de este campo. Aunque las condiciones son de naturaleza técnica, abre nuevas direcciones de investigación y posee valor académico importante.