Xrfgtjtk

I found this exercise in Bollobas: Modern Graph Theory "Construct a triangle-free graph of chromatic number 1526"

It is added not to use results from the chapter about Ramsey Theory.

Now my qestions:

(1) Is there a nice way to construct such a graph?

(2) If yes then what is so special about this specific graph?

My ideas: Grötzsch's theorem states that every triangle-free planar graph may be 3-colored, so we know that we can exclude planar grpahs and focus on non-planar graphs.
I read something about the Mycielskian on http://en.wikipedia.org/wiki/Mycielskian

I think this is the key to the solution but I do not see how to follow a concrete construction.

There are many ways to construct triangle-free graphs with large chromatic number. One well-known construction is Jan Mycielski's, which is described in the Wikipedia article that you cited; I guess you had trouble understanding it. Instead of explaining Mycielski's construction, I will describe another one, which is even less "efficient" (meaning that it produces a bigger graph for a given chromatic number) but maybe slightly simpler.

For a given natural number $ninmathbb N$, let $G_n$ be the following graph with $binom n2$ vertices and $binom n3$ edges: the vertices are the pairs $(x,y)$ of integers with $1le xlt yle n$; for each triple $(x,y,z)$ with $1le xlt ylt zle n$, there is an edge joining vertex $(x,y)$ to vertex $(y,z)$. It is plain to see that $G_n$ is triangle-free. I will show that $G_n$ is $k$-colorable if and only if $nle2^k$. Therefore, if $2^{1525}lt nle2^{1526}$, then $chi(G_n)=1526$.

First, suppose $G_n$ is $k$-colorable; I will show that $nle2^k$. Let $f:V(G_n)to[k]={1,dots,k}$ be a proper vertex-coloring of $G_n$; i.e., for $1le xlt yle n$, the vertex $(x,y)$ gets color $f(x,y)in[k]$. For each $xin[n]={1,dots,n}$, let $S_x={f(u,x):1le ult x}subseteq[k]$. Note that, since $f$ is a proper coloring, the sets $S_1,dots,S_n$ must be distinct; namely, if $1le xlt yle n$, then $f(x,y)in S_ysetminus S_x$, showing that $S_xne S_y$. Thus there are $n$ distinct subsets of $[k]$, i.e., $nle2^k$.

Now, suppose $nle2^k$; I will show that $G_n$ is $k$-colorable. Let $S_1,dots,S_n$ be $n$ distinct subsets of $[k]$, indexed in order of increasing size, so that $|S_1|le|S_2|ledotsle|S_n|$; it follows that $S_ynotsubseteq S_x$ whenever $1le xlt yle n$. Finally, we get a proper coloring $f:V(G)to[k]$ by assigning to each vertex $(x,y)$ a color $f(x,y)in S_ysetminus S_x$.

I do not think there is any single right answer to this question. For me the easiest approach is to take a Kneser graph $K_{3r-1:r}$. (Its vertices are the subsets of size $r$ from a set of size $3r-1$, where two such subsets are disjoint.) By a famous result due to Lovasz, the chromatic number of $K_{n:r}$ is $n-2r+2$,
and so for the graphs I am using it's $r+1$, so take $r=1525$.

I doubt this is the solution Bollobas has in mind.