Sequence A76220 of OEIS enumerates (up to $n=25$) the number $a_n$ of permutations $\sigma$ of $\lbrace 1,\ldots,n\rbrace$ such that $\sigma(i)$ and $\sigma(i+1)$ are coprime for $i=1,\ldots,n-1$.
All these numbers are obviously even for $n>1$.
All these numbers are divisible by $3$ for $n\geq 3$.
All these numbers are divisible by $9$ for $n\geq 5$.
All these numbers are divisible by $5$ for $n\geq 17$.
Such a number $a_n$ is divisible by $k!$ if there are $k-1$ primes larger than $n/2$ and smaller than $n$ (the images of $1$ and of these primes in any permutation contributing to $a_n$ can be arbitrarily permuted).
The above examples suggest however better divisibility properties, suggesting the following problem:
Given an integer $n$, what is the maximal number $k=k(n)\leq n$ such that for every permutation $\sigma$ of $\lbrace 1,\ldots,n\rbrace$ there exists a set $\lbrace a_1,\ldots,a_k\rbrace$ of $k$ elements in $\lbrace 1,\ldots,n\rbrace$ with $\sigma(a_i)$ coprime to $\sigma(a_j\pm 1)$ for all $i$ and $j$ (with $a_j-1$ or $a_j+1$ outside $\lbrace 1,\ldots,n\rbrace$ dropped)?
Can one say something meaningful on the asymptotics of $k(n)$ (e.g., has it sublinear growth)?
Observation: We can of course assume that $a_1,\ldots,a_k$ contains the preimage of $1$ and of all primes larger than $n/2$ in $\lbrace 1,\ldots,n\rbrace$.