EDIT: This question is superseded by Chromatic number of the pancake graph 2
The pancake graphs are described on https://en.wikipedia.org/wiki/Pancake_graph. The WIKI page gives a rather complicated upper bound for $\chi(P_n)$, that does not even a do very good job: it roughly says that $\chi(P_n)$ is at most $n$ minus a small constant.
However for every positive integer $n$ following statement seems to be true:
Theorem: writing $n=3q+r$ with $0\leq r<3$, we have $\chi(P_n)\leq 2q+r$ (so roughly $\chi(P_n)\leq\frac23 n$).
The proof is very short and based on one simple observation:
Claim: the subgraph of $P_n$ induced by all permutations/vertices whose first element is $1$, $2$, or $3$ (or any other set of three different elements from $[n]$) is a disjoint union of even cycles (in fact all cycles have lengths that are a small multiple of $6$).
Proof of claim: Let $H$ be the induced subgraph, $v$ a vertex of $H$. Then there are exactly two possible flips that result in another vertex of $H$ (e.g. $1\cdots3\cdots2\cdots$ can only be flipped to $3\cdots1\cdots2\cdots$ or to $2\cdots3\cdots1\cdots$). This shows that $H$ is $2$-regular, so a disjoint union of cycles. After exactly $6$ flips the three chosen elements are in the same order again. This might not close the cycle since the in-between elements may have changed position, but it certainly guarantees that the length of each cycle is a multiple of $6$.
Proof of theorem: partition the vertices of $P_n$ in $V_0,\ldots,V_q$, where $V_i$ contains all permutations whose first element is $3i+1$, $3i+2$, or $3i+3$. Each induced subgraph $G[V_i]$ is $2$-colorable (by the claim) when $i<q$, and $G[V_q]$ is $r$-colorable (if $r=0$, $G[V_q]$ is empty, if $r=1$, $G[V_q]$ has only isolated vertices, if $r=2$, $G[V_q]$ consists of disjoint copies of $K_2$). Using disjoint color sets for each of the subgraphs gives the desired upper bound.
Please verify this proof, or tell me what is wrong. Even if it is correct, it is probably not allowed to modify the WIKI myself as long as there is no "official" publication, is it?
