Are the following concepts known in graph/group theory, and if Yes, what are they called and where to read about them? Because I do not know better, I gave them placeholder names for now.

1. Transitive edge-colorings of $K_n$

Given a group of permutations $G\subseteq\mathrm{Sym}(n)$ on the $n$ vertices of $K_n$ (the complete graph on $n$ vertices). A transitive edge-coloring on $K_n$ is given by the edge-orbits under $G$, i.e. two edges receive the same color if they belong to the same orbit under $G$. This gives a decomposition of $K_n$ into edge-transitive graphs $\Gamma_1,...,\Gamma_k$ with $G\subseteq\mathrm{Aut}(\Gamma_i)$.

Example. The following transitive coloring was generated by a group $G\subset\mathrm{Sym}(4)$ ismorphic to $\Bbb Z_2\times\Bbb Z_2$. Note that $G$ is a proper subgroup of $\mathrm{Aut}(\Gamma_i)$ for all $\Gamma_i$.

2. Induced transitive edge-colorings

Given an edge-transitive graph $\Gamma$ on $n$ vertices. Then $\mathrm{Aut}(\Gamma)$ induces a transitive edge-coloring on $K_n$ with one of the color classes being $\Gamma$ itself. We say that $\Gamma$ induces the transitive edge-coloring.

Example. The following transitive coloring was generated by $C_6$ (cycle on six vertices). Note that $C_6$ has the strictly smallest automorphism group of all the color classes.

Especially interesting are graphs $\Gamma$ that induce transitive edge-colorings with only connected color classes, because this happens exactly when the $\mathrm{Aut}(\Gamma)$ acts primitively.

3. Transitive decomposition of $K_n$

If all the color classes $\Gamma_1,...,\Gamma_k$ of a transitive edge-coloring induces this coloring, then I call this a transitive decomposition of $K_n$. This means that all the $\Gamma_i$ have the same automorphism group.


  • Any edge-transitive graph $\Gamma$ on $n$ vertices with an edge-transitive complement gives a decomposition of $K_n$ with two colors, one for the edges of $\Gamma$, one for the edges of the complement. Among these graphs are the simultaneously arc-transitive and self-complementary graphs, which are fully enumerated by the Payley graphs, Peisert graphs and another exceptional graph on $23^2$ vertices. Another example is the Petersen graph and its complement, the line graph of $K_5$.

  • A cycle $C_p$ with $p$ prime gives a transitive decomposition of $K_p$ with $(p-1)/2$ colors. All the color classes are isomorphic. The image below shows the transitive decomposition into three $C_7$'s.

  • 5
    $\begingroup$ For concept 1, each colour class is usually called an orbital for the group, and the corresponding graphs are called orbital graphs. (Note that many authors would allow the graphs to digraphs, and would consider the action of the group on ordered pairs, rather than unordered pairs. See symomega.wordpress.com/2012/02/27/… where the distinction is made very clearly, and he decides to call the unordered ones "orbs".) The other two concepts are not far off, but I've never seen them explicitly given names. $\endgroup$ – verret Sep 11 '18 at 21:24
  • 2
    $\begingroup$ The fact you state about transitive edge colourings all being connected if and only if the group is primitive is (if I understand your notation correctly), a theorem of Higman (written in terms of orbitals -- see Verret's comment): D.G. Higman, Intersection matrices for finite permutation groups, J. Algebra 6 (1967), 22–42. $\endgroup$ – Nick Gill Sep 12 '18 at 9:51
  • $\begingroup$ @verret Thank you very much. This part of the linked blog contains two very useful links: a thesis named "Transitive Decompositions of Graphs" (amazing how this is just the exact same name I came up with, there seems to be system in naming things), and a paper named "Homogeneous Factorisation of Complete Graphs with Edge-Transitive Factos" containing these ideas too. Both links on the website broke down, but the content is still available online. I would be happy to see this as an actual answer to this post. $\endgroup$ – M. Winter Sep 12 '18 at 15:04
  • $\begingroup$ @M.Winter Feel free to write this up as an answer! $\endgroup$ – verret Sep 20 '18 at 3: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.