Colorear estrellas

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

El número cromático de la 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 en estrella de un grafo G es una coloración de vértice (adecuada) en la que cada camino en cuatro vértices usa al menos tres colores distintos. De manera equivalente, en una coloración en estrella, los subgrafos inducidos formados por los vértices de dos colores cualesquiera tienen componentes conectados que son grafos en estrella . La coloración en estrella fue introducida por Grünbaum (1973). El número cromático de estrella de G es la menor cantidad de colores necesarios para colorear G en estrella . ${\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 de dos colores son bosques . Si denotamos el número cromático acíclico de un grafo G por ⁠ ⁠ ${\displaystyle \chi _{a}(G)}$ , tenemos que ⁠ ⁠ ${\displaystyle \chi _{a}(G)\leq \chi _{s}(G)}$ , y de hecho cada coloración de estrellas de G es una coloración acíclica.

Nešetřil y Ossona de Méndez (2003) demostraron que el número cromático de estrella está limitado en cada clase menor cerrada propia. Nešetřil y Ossona de Méndez (2006) generalizaron estos resultados a todas las coloraciones de baja profundidad de árbol (la coloración estándar y la coloración de estrella son coloraciones de baja profundidad de árbol con los parámetros 1 y 2 respectivos).

Complejidad

Albertson et al. (2004) demostraron que es NP-completo determinar si , incluso cuando G es un grafo que es tanto planar como bipartito . Coleman y Moré (1984) demostraron que encontrar una coloración estelar óptima es NP-difícil incluso cuando G es un grafo bipartito. ${\displaystyle \chi _{s}(G)\leq 3}$

Referencias

• Albertson, Michael O.; Chappell, Glenn G.; Kierstead, Hal A.; Kündgen, André; Ramamurthi, Radhika (2004), "Coloración sin P4 de dos colores", The Electronic Journal of Combinatorics , 11 (1), doi : 10.37236/1779 , MR  2056078.
• Coleman, Thomas F. ; Moré, Jorge (1984), "Estimación de matrices hessianas dispersas y problemas de coloración de grafos" (PDF) , Programación matemática , 28 (3): 243–270, doi : 10.1007/BF02612334 , hdl : 1813/6374 , MR  0736293.
• Fertin, Guillaume; Raspaud, André; Reed, Bruce (2004), "Coloración de estrellas de gráficos", Journal of Graph Theory , 47 (3): 163–182, doi :10.1002/jgt.20029, MR  2089462.
• Grünbaum, Branko (1973), "Coloraciones acíclicas de grafos planares", Israel Journal of Mathematics , 14 (4): 390–408, doi :10.1007/BF02764716, MR  0317982.
• Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2003), "Coloraciones y homomorfismos de clases cerradas menores", Geometría discreta y computacional: la edición de Goodman-Pollack , Algorithms & Combinatorics, vol. 25, Springer-Verlag, págs. 651–664, MR  2038495.
• Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2006), "Profundidad de á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 estelares y coloraciones acíclicas (1973), presente en Experiencias de Investigación para Estudiantes de Posgrado (REGS) en la Universidad de Illinois, 2008.