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?

  • 1
    $\begingroup$ You probably no longer want an answer here since you have asked the follow-up question math.stackexchange.com/questions/3057032 but for completeness: yes, this argument is correct. (It is not publishable on Wikipedia in its current form, but it may be publishable in DMGT as a follow-up to Konstantinova's paper, since they published that one which proves much weaker bounds. I would take some time to see if you can prove stronger results first.) $\endgroup$ Dec 30, 2018 at 21:46
  • $\begingroup$ @Misha Lavrov: Thanks, I have put a note at the top of the question to tell that it is obsolete now. $\endgroup$ Dec 31, 2018 at 7:21


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.