2
$\begingroup$

[Repost of same question math stack exchange which got no answers]

I'm looking for literature on the following family of graphs:

Call a regular graph $G=(V,E)$ (of regularity degree $d$) nice if there exists a coloring $C:V\to \{ 1,\dots,d \}$ such that each vertex $v$ has precisely one neighbour of each color.

In particular, I'm wondering

Qustion. Is the graph on $V=S_n$ with $x\sim y$ iff $y=x\tau$ for some transposition $\tau$ nice?

Here is what I know so far about nice graphs:

By double counting $\{(x,y):x\sim y, C(y)=i\}$ we see that in a nice graph we have $d\mid n = |V|$ and each color appears on $n/d$ vertices. However this property is not sufficient, as a $6$ cycle is $2$ regular but not nice.

An example of a nice graph: $V=\{0,1\}^8$, $x\sim y$ iff they differ in precisely one bit (Hamming distance 1). The coloring of $(x_0,\dots,x_7)$ is $(x_0\cdot 0)\oplus (x_1\cdot 1) \oplus \dots \oplus (x_7\cdot 7)$, with $\oplus$ denoting xor. (Of course $8$ can be replaced with any power of two).

Improve this question
$\endgroup$
2
  • $\begingroup$ Yes for $n=2, 3$. $\endgroup$
    – Sean Eberhard
    Commented Feb 28 at 12:23
  • 1
    $\begingroup$ Draw a graph on $A_n$ connecting two permutations if they differ by a product of two transpositions. If your coloring exists, it is a proper coloring of this graph. I doubt such exists for a large $n$… $\endgroup$
    – Ilya Bogdanov
    Commented Feb 29 at 10:04

2 Answers 2

Reset to default
3
$\begingroup$

Not for $S_4$. In fact it would take $12$ colors so that every vertex had neighbors of distinct colors. But then there are $(12!)^2$ such colorings!

Because the graph is bipartite, each of the $6$ colors would need to appear twice among the odd permutations and twice among the even permutations.

The $6$ transpositions get the $6$ colors once each since they are the neighbors of the identity. and each color is used once more among the other odd permutations.

The neighbors of (123) are {(12),(13),(23), (1234),(1423),(1243)}
The neighbors of (132) are {(12),(13),(23), (1342),(1324), (1432)}

So the colors of {(14),(24),(34)} must be those of {(1234),(1423),(1243)} but also those of {(1342),(1324), (1432)}. Since each of those colors is only allowed to be used once more among the odd permutations, this is impossible.

To see the $12$ colors claim: Two vertices with a common neighbor must have distinct colors.Make a new graph by instead connecting vertices which must be of distinct colors. That is two disjoint copies of $K_{12}$, one for the even permutations and one for the odd.

Improve this answer
$\endgroup$
1
$\begingroup$

"Nice" graphs are covering graphs of reflexive cliques (looped complete graphs) ${K_n}^\circ$. Definitions of covering graphs and coverings (or locally bijective homomorphisms) often don't apply to looped graphs or multi-graphs (because they don't look at how edges are mapped, only vertices, like the one given on Wikipedia), but since transposition graphs are bipartite, you can use the fact that "bipartite nice" graphs are the same as covering graphs of $K_{n,n}$ (${K_n}^\circ \times K_2$).

They can be enumerated via voltage graphs over $K_{n,n}$, but I don't know the details. See "Locally Constrained Graph Homomorphisms — Structure, Complexity, and Applications" (particularly below Proposition 3), perhaps also "Graphs and their coverings" by Kwak & Nedela (much more in-depth but probably overkill).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .