Encuentre un ejemplo de un triángulo regular libre$4$ - gráfico cromático

Question

Encontrar un ejemplo de un triángulo regular libre de $4$-cromática gráfico

Sé que para cada $k \geq 3$ existe un triángulo libre de $k$-cromática gráfico.

Así que si puedo encontrar un triángulo de libre gráfico de $H$ tal que $\chi(H)=3$, entonces puedo usar el Mycielski de la construcción, para obtener un triángulo de libre gráfico de $G$ tal que $\chi(G)=4$. Sin embargo, la parte regular seguir recibiendo me pegó. Yo trate de alguna extraña ciclo, también probé el gráfico de Petersen, pero todavía no puede conseguir un triángulo regular libre de $4$-cromática gráfico.

Me pregunto si alguien me puede dar una sugerencia, por favor.

Answer 1

Si eres perezoso, puedes consultar todas las gráficas de Wikipedia. El gráfico de Hoffman-Singleton , por ejemplo, es fuertemente regular, tiene circunferencia 5 y tiene el número cromático 4.

Answer 2

Otro ejemplo está dado por Kneser gráficos de $K(n,k)$ con adecuados parámetros.

Por Lovasz teorema, la cromática número de $K(n,k)$ está dado por $n-2k+2$.

Por otra parte, si $n<3k$ tenemos que $K(n,k)$ es de triángulo, por lo tanto:

$\color{red}{K(8,3)}$ es un triángulo libre, $10$-gráfico regular en $56$ vértices con cromática número $\chi=4$.

Sin embargo, el ejemplo mínimo de un triángulo libre, gráfico regular con $\chi=4$ es dada por otro "topológico gráfico", el Clebsch gráfico, con $16$ vértices y el grado $5$.

Answer 3

Discutido este asunto con mi guía después de obtener una respuesta específica por parte de la unión de dos Mycielskian de $C_5$ adecuadamente (por lo $22$ vértices). Él me contó la siguiente técnica, que puede ser generalizado para manejar ese tipo de preguntas.

Construir la Mycielskian de $C_5$ (cualquier triángulo libre $4$-cromática gráfico). Tenemos cinco vértices con grado de $3$, cinco con el grado $4$ y uno con grado de $5$. Hacer cinco copias de este. Añadir un nuevo vértice y unirse a los correspondientes de grado $4$ vértice en cada una de las cinco copias. Hacer esto por el resto de grado $4$ vértices. Para el grado $3$ vértices tomar dos vértices y unirse a dos de ellos para el correspondiente grado $3$ vértice en cada una de las cinco copias. Ahora el gráfico final, que es regular, el triángulo libre y $4$-cromática.

Esta técnica ya se ha publicado (no se puede encontrar el papel).

---

ADDENDUM:

Para este método general, se utiliza el mismo color en todos los cinco copias ($a_i$,$b_i$,...,$e_i$ para$i = 1$$11$) de la Mycielskians (color 1 a 4). Cada título correspondiente 4 vértice de cada uno está conectado a un nuevo vértice (es decir,$a_1$,$b_1$,...,$e_1$, tiene el mismo color que decir 1, está conectada a un nuevo vértice cuyo grado es $5$ que se le puede asignar un color distinto de 1). Hacer esto por el resto de grado 4 vértices ($a_i$,$b_i$,...,$e_i$ para$i = 2$$5$). Cada título correspondiente 3 vértice de cada uno está conectado a dos nuevos vértices (es decir,$a_6$,$b_6$,...,$e_6$, tiene el mismo color que decir 1, está conectado a dos nuevos vértices cuyo grado es $5$ que se le puede asignar un color distinto de 1). Hacer esto por el resto de grado 4 vértices ($a_i$,$b_i$,...,$e_i$ para$i = 7$$10$).

Esto se traduce en un regular $\Delta$libre de $4$-cromática gráfico.

En PARTICULAR RESPONDER a: (no utilizando el método general descrito anteriormente, lo que resultaría en un gráfico de orden $70$)

La siguiente es una particular respuesta a esta pregunta utilizando Mycielskian resultando en un gráfico de orden $22$. Estos son dos copias de Mycielskian de $C_5$. No he dibujado todos los bordes dentro de cada Mycielskian para mejorar la claridad. La izquierda 5 vértices de Mycielskian fueron grado 4 vértices por lo tanto tienen sólo una coincidencia, mientras que la media de los cinco vértices de Mycielskian fueron grado 3 vértices por lo tanto tienen dos elecciones para hacerlos regular.