Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.