It turns out that the approach used in Chromatic number of the pancake graph can be generalized and simplified, leading to even better upper bounds.
Theorem: For all positive integers $n$ and $m$, we have $\chi(P_{n+m})\leq \chi(P_n)+\chi(P_m)$.
To prove this, we define $P_n(k)$ (for $k\in[n]$) to be the subgraph of $P_n$ that consists of all vertices/permutations whose first element is in $[k]$. The mapping $P_n(k)\to P_k$, defined by just removing the elements that are not in $[k]$ from all permutations is clearly a graph homomorphism (it is surjective, but not an isomorphism). This implies that $\chi(P_n(k))\leq\chi(P_k)$. Note that the symmetry of $P_n$ makes that it does not matter if we take the first $k$ elements or any other set of $k$ elements to define $P_n(k)$.
Example, for $n=7$, $k=3$, we map $3417652$ to $312$. A valid swap in $P_7(3)$ must put $1$ or $2$ in the first position, e.g. $3417652\to 1437652$, which maps to $312\to132$.
Now we partition the vertices of $P_{n+m}$ in a set $V$, containing all permutations whose first element is in $[n]$ and a set $W$, containing all permutations whose first element is in $\{n+1,\ldots,n+m\}$. Then $V$ induces $P_{n+m}(n)$, so it is $\chi(P_n)$-colorable and $W$ induces $P_{n+m}(m)$, so it is $\chi(P_m)$-colorable.
By using disjoint color sets, this implies that $\chi(P_{n+m})\leq\chi(P_n)+\chi(P_m)$, finishing the proof.
Examples:
We know that $\chi(P_5)=3$, so $\chi(P_{10})\leq 6$, $\chi(P_{15})\leq9$, etc.
We know that $\chi(P_7)=4$, so $\chi(P_{14})\leq 8$, $\chi(P_{21}\leq12)$, etc. This gives a general upper bound of approximately $\frac47n$.
As soon as we can improve the upper bound for some pancake graph, we can improve the upper bounds for all larger pancake graphs.
I strongly believe the theorem is correct and unknown, and the obtained upper bounds are better than we have until now.
Please verify my claims, or tell me what is wrong with them.
Thanks to Zachary Hunter, whose insight made both the theorem and its proof more elegant.
