Coloración de estrellas
En matemáticas de 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 usa al menos tres colores distintos. De manera equivalente, en una coloración estelar, los subgrafos inducidos formados por los vértices de dos colores cualesquiera tienen componentes conectados que son gráficos estelares . 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 el color de estrella 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 , tenemos que , y de hecho cada coloración estelar de G es una coloración acíclica.
Nešetřil & Ossona de Mendez (2003) ha demostrado que el número cromático estrella está limitado en cada clase cerrada menor adecuada . Nešetřil & Ossona de Mendez (2006) generalizaron aún más estos resultados a todas las coloraciones de profundidad de árbol baja (la coloración estándar y la coloración de estrella son coloraciones de profundidad de árbol baja con los respectivos parámetros 1 y 2).
Fue demostrado por Albertson et al. (2004) que es NP-completo determinar si , incluso cuando G es un grafo que es a la vez plano y bipartito .Coleman y Moré (1984) demostraron que encontrar una estrella de coloración óptima es NP-difícil incluso cuando G es un gráfico bipartito.
