Construcción de todas digráficas 3 y 4-dicromáticas críticas, con un número fijo de arcos simétricos, de orden mínimo, usando operaciones de Hajós

Ponente(s): Juan Carlos García Altamirano, Mika Olsen Jorge Cervantes Ojeda

Una coloración de vértices de una digráfica es acíclica si no hay ciclos dirigidos monocromáticos. El número dicromático de una digráfica D es el número mínimo de colores de una coloración acíclica de D, denotado por dc(D). Una digráfica D es r-crítica si dc(D) y dc(H) < r para cualquier subdigráfica propia H de D. En 2020 Bang-Jensen et al. extendieron la conocida construcción de Hajós de gráficas para digráficas y demostraron que: a partir de copias de la digráfica simétrica completa con r vértices, D(Kr), se puede construir cualquier digráfica r-crítica mediante uniones dirigidas de Hajós e identificaciones de vértices no adyacentes. Sin embargo, a los autores les apenó mucho no poder construir, ni siquiera, al ciclo simétrico D(C5) a partir de copias de D(K3), y lo dejaron como problema abierto. Nosotros resolvimos ese problema adaptando un algoritmo genético y generalizamos la construcción para obtener cualquier ciclo simétrico impar a partir de D(K3). Ahora, en esta pática, presentamos la construcción un conjunto de digráficas más complejas: las digráficas 3 y 4-dicromáticas críticas, con un número fijo de arcos simétricos, de orden mínimo; a partir de D(K3) y D(K4), respectivamente.