3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Have you seen the paper Elena Konstantinova, Chromatic Properties of the Pancake Graphs, Discussiones Mathematicae Graph Theory 37(3):777-787 · August 2017? $\endgroup$ Dec 30, 2018 at 17:58
  • 1
    $\begingroup$ Yes, I have. Her results seem to be the (very weak) results that are on the WIKI page. They are OK for some small values of $n$, but fail completely for larger values of $n$. $\endgroup$ Dec 30, 2018 at 18:02
  • $\begingroup$ Btw, I have tried to contact her, but the email address in the article is considered a bad address. $\endgroup$ Dec 30, 2018 at 18:10

1 Answer 1

2
$\begingroup$

Your claim is correct. In fact, by this logic, you could say the slightly stronger claim: $\chi(P_n) \leq \chi(P_a)+\chi(P_b)+\chi(P_c)$ where $a,b,c$ are non-negative integers and $a+b+c=n$.

However, I think the chromatic numbers will simply grow too slow for this method to yield tight bounds.

$\endgroup$
2
  • 1
    $\begingroup$ Regarding your last point; it appears we do not even know if $\chi(P_n) > 4$ for any $n$. $\endgroup$ Dec 30, 2018 at 21:49
  • $\begingroup$ Great. Your insight has lead to a revision that is not stronger, but certainly more elegant. $\endgroup$ Dec 31, 2018 at 7:36

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.