Partición trazable de los posibles k-colores de vértices de un grafo por estabilidad e inestabilidad local.

Question

Una k-coloración o k-etiquetado de los vértices de un grafo no dirigido de un solo componente G con $n$ Los vértices pueden ser una coloración adecuada o no. Si no es una coloración adecuada, de manera que cada vértice tiene vecinos en sus aristas que son de un color o etiqueta diferente, entonces para cada etiquetado posible, es posible contar el número de vértices que tienen una coloración adecuada localmente como un número entero $x \in \{0,n\}$ y los que no $y = n-x$ . Llamemos "estables" a los vértices que están localmente coloreados correctamente, y "inestables" a los que tienen al menos un vecino con la misma etiqueta de color. El conjunto de todos los etiquetados posibles, de los cuales hay $k^n$ puede dividirse en $n+1$ por la métrica de cuántos vértices son inestables para cada coloración.

¿Cuál es el tamaño de cada partición desde 0-inestable hasta n-inestable? ¿Existe un nombre particular para este tipo de partición? Obviamente, si estamos estableciendo $k=2$ entonces el tamaño de la partición de 0-inestable es 2 si el grafo G es bipartito y permite una coloración propia-2; si $k=3$ y el grafo es 3-colorable, entonces el tamaño de la partición de 0-inestable es 6; etc.

Por supuesto, esta partición puede calcularse por métodos de fuerza bruta en tiempo exponencial ( $k^n$ ) enumerando todos los posibles etiquetados con $k$ etiquetas en un gráfico con $n$ vértices.

¿Para qué clases de grafos es trazable el problema? Por ejemplo, como se describe a continuación en una respuesta, para los grafos en estrella $S_m$ con $m$ hojas y $n=m+1$ vértices, la distribución es casi la distribución binomial, con $2$ como el tamaño de la partición 0-inestable, cero como el tamaño de la partición 1-inestable, y $2 {m \choose j-1}$ como el tamaño del $j$ -partición inestable donde $1\lt j \le n$ .

ABmd

Answer 1

Si lo limitas a clases específicas de grafos, por ejemplo, grafos en estrella, puedes obtener algunas respuestas. Para un gráfico de estrella $S_m$ con un vértice en el centro y $m$ vértices conectados al centro, dando lugar a un gráfico $G$ con $n=m+1$ vértices y $m$ se puede calcular que para $k=2$

Si el vértice central está etiquetado en negro, entonces la única coloración "0-inestable" es aquella en la que todas las hojas son blancas. Si alguna de las hojas es también negra, digamos $j$ de la $m$ hojas son negras mientras el centro también es negro, entonces el centro y esas $j$ las hojas negras son inestables, dejando $m-j$ deja como nodos estables. Hay $m \choose j$ = ( $m$ elija $j$ ) formas de colorear $j$ de la $m$ hojas como el negro.

Lo mismo ocurre con las etiquetas de color invertidas si el centro está etiquetado en blanco. Así, para $k=2$ para el etiquetado bicolor de un gráfico de estrellas $S_m$ con $m$ hojas y $n=m+1$ vértices, los tamaños de las particiones de todos los posibles bicolores son los siguientes:

|{0 inestable}| = 2

|{1 inestable}| = 0

|{r inestable}| = $2 \times$ ${m}\choose{r-1}$ para $ 2 \le r \le n$ con $r \in Z $

El tamaño de la partición 1-inestable es siempre cero para esta familia de grafos. El tamaño de la partición 1-inestable es siempre cero para cualquier gráfico y para cualquier $k$ porque la inestabilidad se produce en una arista que une dos vértices con la misma etiqueta de color, por lo que siempre se crean dos vértices inestables si es que hay algún vértice inestable.

La suma de todos estos tamaños de particiones es $2^n$ por lo que todas las posibles $2^n$ colores de la $n=m+1$ gráfico en estrella de vértices $S_m$ se han contabilizado. Se puede hacer un cálculo similar para los gráficos de estrellas para $k>2$ .

Apurva

Answer 2

En general, esto es difícil, a menos que se tenga en mente una estructura gráfica específica. Para encontrar el número de $k$ -colores de su gráfico $G$ es equivalente a calcular su polinomio cromático y esto es NP-difícil. Cuando se tiene $r$ vértices inestables, esto equivale a encontrar un subgrafo de $H$ su gráfico $G$ de tamaño $r$ sin vértices aislados y luego encontrar el número de $k$ -colores de $G/\sim$ donde identificamos los puntos que pertenecen a la misma componente conectada en $H$ . No veo una razón para esperar una respuesta manejable en general.

---

Dado que nos interesan los grafos cíclicos, dejemos que el polinomio cromático del grafo cíclico en $n$ los vértices sean $\pi_n(x)$ . Dejemos que $g_n(k,m)$ sea el número de $m$ colorantes donde hay $k$ vértices inestables. Entonces tenemos $$g_n(0,m)=\pi_n(m)=(m-1)^n+(-1)^n(m-1).$$ Claramente tienes $g_n(1,m)=0$ y calcular $g_n(k,m)$ denotamos por $p(k,r)$ el número de particiones cíclicas de $n$ en $r$ partes de tamaño en $\geq 2$ y $n-k$ monotonales (esto tiene una fórmula cerrada que no es muy difícil de derivar). Ahora tenemos $$g_n(k,m)=\sum_{r\geq 1}p(k,r)g_{n-k+r}(0,m)$$ por la obvia correspondencia de que cada bloque de la partición es monocromático. En otro orden de cosas, puede resultar interesante el artículo "A new two-variable generalization of the chromatic polynomial" de K. Dohmen, A. Ponitz y P. Tittmann. En él se habla de una forma similar, pero no igual, de considerar las coloraciones con vértices "propios" y "no propios".