What is the chromatic number of the graph whose vertices dimension $n-2$ subsimplicies of $\Delta^n$ and an edge between two vertices is given if the two associated $n-2$ vertices are contained in the same $n-1$ subsimplex?

Question

Let us first remark that all of this takes place on the boundary of $\Delta^n$. The question that I wanted to solve that led to the question in the title is as follows: Let $f:\Delta^{n-1}\hookrightarrow\Delta^n$ be an injective map. What I would have liked to do is to extend that map to a map, $\tilde{f}:\partial\Delta^n\hookrightarrow\Delta^n$ such that the restriction of $\tilde{f}$ on any the n-1 simplices of the boundary is the original map $f$ up to an action of the symmetric group on n letters.

One can see with a little thought that the condition needed to be able to obtain this is as follows: First we construct the graph mentioned in the question. To recapitulate, the vertices of this graph are the set of n-2 simplicies. We then attach an edge between two vertices if the two n-2 simplices are contained in the same n-1 simplex. Let us call this graph $X_n$ for lack of better notation. One may extend build the $\tilde{f}$ if (and only if I believe) if the graph constructed is $n$ colorable.

Now by working it out by hand, I showed that this is impossible for $n=2$, possible for $n=3$ impossible for $n=4$ and I believe that it is impossible for dimensions above. What is a proof for this fact? I did the work by hand for the cases I mentioned. It would be even better to know the actual chromatic number for these graph.

Answer 1

It is known that the complete graph $K_{2m}$ has a 1-factorization (e.g., http://en.wikipedia.org/wiki/Graph_factorization). This means that its set of edges can be written as a disjoint union of $2m-1$ complete matchings $M_1, \dots, M_{2m-1}$, each with $m$ edges. If $e$ is an edge of $K_{2m}$ regarded as a 2-element subset $\lbrace i,j\rbrace$ of $[2m] = \lbrace 1,2,\dots, 2m\rbrace$, then let $\bar{e}$ denote the complement $[2m]-\lbrace i,j\rbrace$, and let $\bar{M}_i =\lbrace \bar{e}\colon e\in M_i\rbrace$. Color the elements of $\bar{M}_i$ with the color $i$. This gives a proper coloring of the $2m-3$ simplices of $\Delta^{2m-1}$ in $2m-1$ colors.