Coloring a graph, special case I have a question that might be an open problem, I don't know for sure but if you do know the answer please let me know.
Consider a set with $2n$ elements, now consider those subsets of it that have $n$ elements in them. To each subset, assign a graph vertex. Now, connect two vertices if and only if the intersection of their sets have at most one elements in it. I want to show that the "chromatic number" (which I define below) for $n>3$ is equal to 6.
  Chromatic number, by the way, is the least number of colors by which we can paint the vertices such that no two vertices that are adjacent end up with the same color.
What i was looking for appears to be a special case of generalized kneser graph (where s=1, which means two vertices are allowed to be connected if their corresponding sets intersect in 1 or 0 elements). I searched some articles yet i could not find a formula for it's chromatic number. again, I want to prove that the chromatic number for $KG_{(2n,n,1)}$ is 6 for n > 3. 
 A: Here is a partial solution, showing that 6 colors are sufficient.
The vertices of our graph $KG_{2n,n,1}$ are the $n$-element subsets of $[2n]$.
We prescribe a coloring for a given subset $A$.
Assign color red if $A$ contains 1 and 2.
Assign color green if $A$ contains neither 1 and 2.
If $A$ contains 1 and not 2, color it blue when it contains 3, and yellow otherwise.
If $A$ contains 2 and not 1, color it white when it contains 3, and black otherwise.
This clearly assigns a color to each subset, and uses exactly 6 colors, so
we only need to show that two vertices with the same color cannot be adjacent.
Two red vertices contain both 1 and 2, so they are not adjacent.
Similarly two blue vertices contain both 1 and 3, two white vertices contain both 2 and 3.
Two green vertices contain neither 1 nor 2, so they must have an intersection of two other elements,
so they are not adjacent.
Similarly two yellow vertices contain neither 2 nor 3, two black vertices contain neither 1 nor 3.
This shows $\chi(KG_{2n,n,1})\leq 6$.
For $n=2$ the graph is simply $K_6$ so 6 colors are required.
For $n=3$ a computer easily shows that 6 colors are required.
I expect that 6 colors are required for all $n$ but have not yet been able to prove it.
