Coloración de estrellas

Coloración de gráficos en la que cada ruta de 4 vértices utiliza ≥3 colores

El número cromático de estrella del gráfico de Dyck es 4, mientras que el número cromático es 2.

En el campo matemático de la teoría de grafos , una coloración de estrella de un gráfico G es una coloración de vértice (adecuada) en la que cada camino en cuatro vértices utiliza al menos tres colores distintos. De manera equivalente, en una coloración de estrellas, los subgrafos inducidos formados por los vértices de dos colores cualesquiera tienen componentes conectados que son gráficos de estrellas . Grünbaum (1973) introdujo la coloración de estrellas. El número cromático de estrella de G es la menor cantidad de colores necesarios para crear el color de estrella G. ${\displaystyle \chi _{s}(G)}$

Una generalización de la coloración de estrellas es el concepto estrechamente relacionado de coloración acíclica , donde se requiere que cada ciclo use al menos tres colores, por lo que los subgrafos inducidos por dos colores son bosques . Si denotamos el número cromático acíclico de un gráfico G por , tenemos eso y, de hecho, cada coloración estelar de G es un colorante acíclico. ${\displaystyle \chi _{a}(G)}$ ${\displaystyle \chi _{a}(G)\leq \chi _{s}(G)}$

Nešetřil y Ossona de Méndez (2003) han demostrado que el número cromático de estrella está limitado a cada clase cerrada menor adecuada. Nešetřil y Ossona de Méndez (2006) generalizaron aún más este resultado a todas las coloraciones de baja profundidad de los árboles (la coloración estándar y la coloración de estrellas son coloraciones de baja profundidad de los árboles con los parámetros 1 y 2 respectivos).

Complejidad

Fue demostrado por Albertson et al. (2004) que es NP-completo determinar si , incluso cuando G es un gráfico que es a la vez plano y bipartito . Coleman y Moré (1984) demostraron que encontrar una coloración de estrella óptima es NP-difícil incluso cuando G es un gráfico bipartito. ${\displaystyle \chi _{s}(G)\leq 3}$

Referencias

• Albertson, Michael O.; Chappell, Glenn G.; Kierstead, Hal A.; Kündgen, André; Ramamurthi, Radhika (2004), "Colorear sin P4 de 2 colores", The Electronic Journal of Combinatorics , 11 (1), doi : 10.37236/1779 , MR  2056078.
• Coleman, Thomas F .; Moré, Jorge (1984), "Estimación de matrices dispersas de Hesse y problemas de coloración de gráficos" (PDF) , Programación matemática , 28 (3): 243–270, doi : 10.1007/BF02612334 , hdl : 1813/6374 , MR  0736293.
• Fertín, Guillaume; Raspaud, André; Reed, Bruce (2004), "Coloración de gráficos con estrellas", Journal of Graph Theory , 47 (3): 163–182, doi :10.1002/jgt.20029, MR  2089462.
• Grünbaum, Branko (1973), "Coloraciones acíclicas de gráficos planos", Israel Journal of Mathematics , 14 (4): 390–408, doi :10.1007/BF02764716, MR  0317982.
• Nešetřil, Jaroslav ; Ossona de Méndez, Patrice (2003), "Colores y homomorfismos de clases cerradas menores", Geometría computacional y discreta: The Goodman-Pollack Festschrift , Algoritmos y combinatoria, vol. 25, Springer-Verlag, págs. 651–664, SEÑOR  2038495.
• Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2006), "Profundidad del árbol, coloración de subgrafos y límites de homomorfismo", European Journal of Combinatorics , 27 (6): 1022–1041, doi :10.1016/j.ejc.2005.01.010, MR  2226435.

enlaces externos

• Coloraciones de estrellas y coloraciones acíclicas (1973), presente en Research Experiences for Graduate Students (REGS) de la Universidad de Illinois, 2008.