# Triangle free graphs with large chromatic number

I am trying to understand the proof of Theorem 2 given here. (Page 5) The theorem states that $\forall k\exists$ a triangle free graph $G$ with $\chi(G)>k$. The proof constructs such a $G$ as $G=A_kA_{k-1}\cdots A_0(G_0)$, where $A_0(G_0)$ is defined as the amalgamation of the graph $G_0$(which is a previously constructed triangle free $(k+1)$-partite graph having partite sets $V_0,\cdots V_k$, with the property that if it is $k$-colored with each partite set monochromatic then there is a monochromatic edge) on $V_0$.

What is not clear to me is why $G$ will contain a copy of $G_0$ with each class monochromatic. By a previous proposition $A_0(G_0)$ contains a copy of $G_0$ with $V_0$ monochromatic, say red. Now $A_1A_0(G_0)$ contains a copy of $A_0(G_0)$ with its second partite set monochromatic say blue. This does not mean that $V_1$ of $G_0$ is blue.

I would be grateful if someone could resolve my confusion. Thanks for reading through this post.

-
You probably already know this but for every $g \geq 3$ and $k \geq 1$ there are graphs with girth $g$ and chromatic number larger than $k$. This is somehow easy to prove using the probabilistic method. – Jernej Dec 6 '12 at 9:37
Yes, I have seen that proof. I am however interested in the above proof for another reason: The same technique is used in constructing a graph not containing a $K_4$ which always contain a monochromatic $K_3$ when the edges are $2$-colored. – Shahab Dec 6 '12 at 9:56

It seems that it should be possible to employ Proposition 1 inductively to prove the desired result. Take the case of $A_1(A_0(G_0))$.

Let $G_0$ be the $(k + 1)$-partite graph with parts $V_0$, $V_1$, $\ldots\,$, $V_k$ such that if $G_0$ is $k$-colored with each $V_i$ monochromatic then there exists an edge in $G_0$ whose endpoints have the same color.

It's important to note that if $G_0$ is $(k + 1)$-partite, then the amalgamation $A_i(G_0)$ is also $(k + 1)$-partite. This is not made explicit in the notes linked to above (see my and Brian M. Scott's comments below).

The amalgamation method was introduced by Nesetril and Rödl. I believe that this paper is where it first appeared. The definition of the amalgamation of a graph $G$ over another graph $H$ that is given in the "Preliminaries" section of that paper makes clear that if $G$ is $(k + 1)$-partite, then the amalgamation is also $(k + 1)$-partite.

Proof: Color $A_1(A_0(G_0))$ with $k$ colors. By Proposition 1, there exists a set $B \subseteq W_1$ (where $B$ has the same size as the first class of $A_0(G_0)$) such that $(A_0(G_0))_B$ has monochromatic 1st class. Now restrict the $k$-coloring to $(A_0(G_0))_B$. The key observation is that every copy of $G_0$ in $(A_0(G_0))_B$ has its 1st class $V_1$ monochromatic. Now, by applying Proposition 1 to $(A_0(G_0))_B$, there exists a copy of $G_0$ that also has monochromatic 0th class $V_0$.

One can apply the same reasoning inductively to $A_k(A_{k-1}( \cdots A_0(G_0)\cdots ))$ to find a copy of $G_0$ with each class monochromatic. By definition of $G_0$, there must be a monochromatic edge.

-
Thanks but I don't understand why your key observation is true. Could you be a little more explicit? – Shahab Dec 6 '12 at 14:50
@Shahab Figure 1 of the linked document suggests to me that for all $j \neq i$, the $j$th class of the amalgamation $A_i(G)$ is the union of the $j$th classes of the copies $G_A$ of $G$. Hence, if the $j$th class of $A_i(G)$ is monochromatic, then the $j$th class of each copy $G_A$ is also monochromatic. – Andrew Uzzell Dec 6 '12 at 16:13
@Shahab: I didn’t mention it in my explanation of the amalgamation, but I agree with Andrew’s identification of its vertex classes. – Brian M. Scott Dec 6 '12 at 18:52
@Shahab It seems that if $G$ is $r$-partite, then the amalgamation should indeed also be $r$-partite--see my updated answer for details. – Andrew Uzzell Dec 7 '12 at 11:05