Construction of a triangle-free graph of chromatic number $1526$

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 $n\in\mathbb 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 $1\le x\lt y\le n$; for each triple $(x,y,z)$ with $1\le x\lt y\lt z\le 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 $n\le2^k$. Therefore, if $2^{1525}\lt n\le2^{1526}$, then $\chi(G_n)=1526$.

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

Now, suppose $n\le2^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|\le\dots\le|S_n|$; it follows that $S_y\not\subseteq S_x$ whenever $1\le x\lt y\le 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_y\setminus 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.