Grafos libres de triángulos con gran número cromático

Question

Estoy tratando de entender la prueba del Teorema 2 dada aquí . (Página 5) El teorema afirma que $\forall k\exists$ un gráfico sin triángulos $G$ con $\chi(G)>k$ . La prueba construye tal $G$ como $G=A_kA_{k-1}\cdots A_0(G_0)$ , donde $A_0(G_0)$ se define como el amalgama del gráfico $G_0$ (que es un triángulo libre previamente construido $(k+1)$ -grafo partitivo que tiene conjuntos partitivos $V_0,\cdots V_k$ con la propiedad de que si es $k$ -coloreado con cada conjunto de particiones monocromáticas entonces hay una arista monocromática) en $V_0$ .

Lo que no me queda claro es por qué $G$ contendrá una copia de $G_0$ con cada clase monocromática. Por una proposición anterior $A_0(G_0)$ contiene una copia de $G_0$ con $V_0$ monocromático, por ejemplo, rojo. Ahora $A_1A_0(G_0)$ contiene una copia de $A_0(G_0)$ con su segundo conjunto de partita monocromática digamos azul. Esto no significa que $V_1$ de $G_0$ es azul.

Agradecería que alguien pudiera resolver mi confusión. Gracias por leer este post.

Answer 1

Parece que debería ser posible emplear la Proposición 1 de forma inductiva para demostrar el resultado deseado. Tomemos el caso de $A_1(A_0(G_0))$ .

Dejemos que $G_0$ sea el $(k + 1)$ -Gráfico de partes con partes $V_0$ , $V_1$ , $\ldots\,$ , $V_k$ de manera que si $G_0$ es $k$ -coloreado con cada $V_i$ monocromática entonces existe una arista en $G_0$ cuyos extremos tienen el mismo color.

Es importante tener en cuenta que si $G_0$ es $(k + 1)$ -parte, entonces la amalgama $A_i(G_0)$ también es $(k + 1)$ -parte. Esto no se hace explícito en las notas enlazadas arriba (ver mis comentarios y los de Brian M. Scott más abajo).

El método de amalgama fue introducido por Nesetril y Rödl. Creo que este documento es donde apareció por primera vez. La definición de la amalgama de un gráfico $G$ sobre otro gráfico $H$ que se da en la sección "Preliminares" de ese documento deja claro que si $G$ es $(k + 1)$ -partita, entonces la amalgama es también $(k + 1)$ -parte.

Prueba: Color $A_1(A_0(G_0))$ con $k$ colores. Por la Proposición 1, existe un conjunto $B \subseteq W_1$ (donde $B$ tiene el mismo tamaño que la primera clase de $A_0(G_0)$ ) tal que $(A_0(G_0))_B$ tiene una primera clase monocromática. Ahora restringe el $k$ -coloración a $(A_0(G_0))_B$ . La observación clave es que cada copia de $G_0$ en $(A_0(G_0))_B$ tiene su primera clase $V_1$ monocromática. Ahora, aplicando la Proposición 1 a $(A_0(G_0))_B$ existe una copia de $G_0$ que también tiene clase 0 monocromática $V_0$ .

Se puede aplicar el mismo razonamiento de forma inductiva a $A_k(A_{k-1}( \cdots A_0(G_0)\cdots ))$ para encontrar una copia de $G_0$ con cada clase monocromática. Por definición de $G_0$ debe haber un borde monocromático.