Intersecciones de grafos completos k-partitos

Question

Pregunta: ¿Existe una caracterización de los gráficos que surgen como intersecciones de una familia de grafos completos $k$ -de las partes en el mismo conjunto (finito) de vértices?

Está claro que todo gráfico de este tipo es $k$ -colable. Además, cada $k$ -colorables puede extenderse a un gráfico completo $k$ -Gráfico parcial.

Tal vez la respuesta a mi pregunta sea " $k$ -colorable gráficos", pero en cierto modo lo dudo.

Answer 1

Para cada $k$ -coloración de un gráfico $G$ Hay un completo $k$ -de la parte en la que se encuentra el gráfico en el que $G$ se incrusta como un subgrafo de extensión. Supongamos que $u$ y $v$ son vértices de $G$ tal que en cualquier $k$ -coloración, se les asignan colores diferentes. Entonces serán adyacentes en cualquier $k$ -extensión de la parte. (Podríamos decir que estos vértices son "moralmente adyacentes", pero nótese que esto depende de $k$ implícitamente).

Cualquiera de forma única $k$ -Gráfico coloreable que no está completo $k$ -no es la intersección de su $k$ -participación de incrustaciones.

Para otro ejemplo, considere el gráfico construido como sigue. Sea $H$ con el conjunto de vértices $\{1,2,3,4\}$ , sea el gráfico obtenido a partir de $K_4$ eliminando la arista $34$ . Entonces, en cualquier coloreado de 3 los vértices $3$ y $4$ obtener el mismo color. Ampliar $H$ uniendo un nuevo vértice $5$ a $4$ ; llama al nuevo gráfico $H_5$ . Entonces, en cualquier coloreado a 3, los vértices 3 y 4 obtienen el mismo color, y los vértices 4 y 5 obtienen colores diferentes. Por lo tanto, 3 y 5 obtienen colores diferentes en cualquier tricolor, aunque no sean adyacentes. De ello se deduce que la intersección de las incrustaciones tripartitas completas de $G$ contiene la arista $35$ . (El gráfico $H_5$ no es únicamente 3-colorable).

No veo ninguna forma de caracterizar los grafos que contienen un par de vértices moralmente adyacentes, pero la respuesta a la pregunta no es " $k$ -Gráficos coloreables".