Estudio de extensiones de coloreo impar en grafos planares

Abstract

Este trabajo se enmarca en la teoría de grafos, específicamente en el estudio de variantes del coloreo impar en grafos planares. Motivado por aplicaciones en asignación de frecuencias y por recientes desarrollos teóricos, se analizan dos extensiones del coloreo impar: la coloración impar casi fuerte, introducida en esta investigación, y la coloración 2-impar, propuesta previamente en la literatura. Ambas nociones imponen restricciones de paridad en las ocurrencias de colores dentro del vecindario de cada vértice. El objetivo principal es estudiar el comportamiento de los números cromáticos asociados a estas coloraciones en distintas subclases de grafos planares. En primer lugar, se establecen cotas superiores ajustadas para árboles, grafos unicíclicos, ruedas y escaleras de Möbius, mostrando que estas estructuras permiten una caracterización precisa de los nuevos parámetros cromáticos. En particular, se evidencia que las coloraciones impar casi fuerte y 2-impar no son comparables en general, aunque coinciden en ciertas clases específicas. El foco central del trabajo se sitúa en los grafos outerplanares maximales. Se demuestra que, en esta clase, los números cromáticos impar casi fuerte y 2-impar coinciden, y que ambos están acotados superiormente por 6. La demostración utiliza una construcción recursiva de estos grafos junto con técnicas de permutación de colores y el análisis de testigos, que permiten extender coloraciones manteniendo las propiedades de paridad requeridas. Además, para la subclase de grafos outerplanares maximales sin “triángulos internos”, se prueba que la cota se reduce a 5 y que esta es óptima. Finalmente, se exploran clases más amplias de grafos planares, incluyendo grafos outerplanares no maximales y triangulaciones tipo stack (3-árboles planares). En estos casos, se obtienen nuevas cotas superiores, destacando que 7 colores son suficientes para grafos outerplanares generales y que 10 colores bastan para la coloración 2-impar en triangulaciones stack. En conjunto, el trabajo aporta nuevas definiciones, cotas mejoradas y herramientas metodológicas que contribuyen al entendimiento de las coloraciones impares en grafos planares y abren nuevas líneas de investigación en el área.