Which 3-regular graphs are Schreier coset graphs?

Question

Given a group $G$ and a subgroup $H$ the Schreier coset graph (w.r.t. some set $S$ of $G$) is the directed (and labelled) graph whose vertices are the cosets of $H$ (i.e. the set $G/H$) and $x \sim y$ if there is a $s \in S$ so that $x = sy$.

When $S$ is symmetric (i.e. $s \in S \implies s^{-1} \in S$), then one can associate to this graph an undirected graph (by replacing the two edges with opposite directions and labels $a$ and $a^{-1}$ by an undirected edge). Note that it could happen that $a = a^{-1}$ which is unproblematic unless the edge makes a loop. So in the undirected graph one needs to distinguish the degree 2 loops (which come from $a$ and $a^{-1}$ acting trivially on the coset $x$) and the degree 1 loops (which come from $a = a^{-1}$ acting trivially on the coset $x$).

Using this construction (and this convention for loops), a Schreier graph is always a regular graph (of degree $|S|$).

Given an even degree regular graph (without "degree 1" loops), then it is possible to find a group $G$ (a free group actually), subgroup $H <G$ and set $S$ so that this graph is a Schreier coset graph. This is a result of J.L.Gross, see https://doi.org/10.1016/0095-8956(77)90068-5.

Question: Assume $\Gamma$ is a an 3-regular graph. What are the necessary conditions for $\Gamma$ to be a Schreier Graph?

I'm fine with any answers which assumes that $\Gamma$ is loopless. Sufficient conditions are somehow much more easy to come by (see examples below).

A combinatorial way to ask the question is to find a labelling of the directed graph underlying $\Gamma$ so that $a^{-1}$ always labels an edge in the opposite direction to $a$ (with the pesky exception of those degree 1 loops).

Example (of a sufficient condition for a loopless graph): if the graph has a perfect matching (a.k.a. 1-factor), then you can label these edges by an element $a = a^{-1}$. There only remains an even degree graph, so by the result of Gross you can get away with $G = F * \mathbb{Z}_2$ where $F$ is the free group mentioned above and $a$ is the generator (and only non-trivial element of $\mathbb{Z}_2$).

Example (continued): every 3-regular bridgeless (i.e. without a cut-edge) graph has a 1-factor (a result of Petersen again). So every 3-regular bridgeless graph is a Schreier graph. In particular, the Petersen graph (or any other snark) are Schreier graphs.

Note that an element $a \in S$ so that $a \neq a^{-1}$ need not always label a 2-factor of $\Gamma$. It just needs to label a spanning subgraphs whose connected components are either edges or cycles (so a mix of 1-factor and 2-factor).

[EDIT]

Non-example: There is an example of an 3-regular graph which is not a Schreier graph. It's sometimes called the "no perfect matching graph", see http://mathworld.wolfram.com/PerfectMatching.html (you have to remove three edges in order to make the graph on that page 3-regular).

This non-example builds a lot on the fact that there are many bridges.

[EDIT]

If there is a way to colour the edges in $k$-colours (and the graph is $k$-regular), then this gives a way to turn the graph in a Schreier graph. (Every element is so that $a = a^{-1}$ and the group $G$ is a free product of $k$ copies of $\mathbb{Z}_2$.)

[EDIT]

It thought that a result of M.Kano see https://doi.org/10.1016/0095-8956(86)90025-0 would give the necessary decomposition of the graph for odd degrees $\geq 5$, but this turns out to be incorrect.

Graphs which cannot be coloured are sometimes called of "class 2" (see Vizing's theorem). Although the Petersen graph (or any snark) is of "class 2", it is a Schreier graph (so being of class 1 is not a necessary condition).

Answer 1

Here are some usefull facts, and some historical details.

Every $2d$-regular graph (without loops of degree 1) is isomorphic to a Schreier graph.

The results for finite graphs is due to Gross. The result for locally finite graphs follows by compacity and was probably one of this well-known "folklore result" for long. To my knowledge, the first written proof of it can be found in "Some problems of the dynamics of group actions on rooted trees" by R. Grigorchuk 2011. But it has since be "reproven" many times (by J. Cannizzo in 2013, in my own phd thesis around the same time, ...).

A (2d+1)-regular graph (without loops of degree 1) is isomorphic to a Schreier graph if and only if it has a perfect matching.

This follows from the previous fact. See for example ARG's answer.

Every countable vertex transitive graphs is isomorphic to a Schreier graphs.

The finite case was done by C. Godsil and G. Royle in 2001. I did (circa 2013) the locally finite case in my phd thesis, using results of Aharoni on matchings in infinite graphs. An independant proof of it was published by Csoka and Lippner in 2017 https://ems.press/journals/ggd/articles/14727. Finally, the countable case was done by M. Hamman and A. Wendland in the appendix of https://arxiv.org/abs/2007.06432

Up to a double cover, any locally finite regular graphs is isomorphic to a Schreier graph.

See https://arxiv.org/pdf/2010.06431.pdf, which is intended as a small note for reference.

Here is the skeleton of the proof. Let $G$ be a locally finite graph. If $G$ is bipartite, put $K=G$. Otherwise, put $K=G\times C_2$. Then $K$ is connected, bipartite (and hence without loops of degree 1), regular and covers $G$. Since $K$ is bipartite and regular it has a perfect matching. The desired result follows.

Answer 2

[community wiki since it's my own question]

The answer is actually simple once the convention on degrees is clear (which it apparently was not at the time of writing)

Answer: If $k$ is odd, a $k$-regular loopless graph is a Schreiers graph if and only if it has a matching.

First note that elements $a \in S$ so that $a \neq a^{-1}$ necessarily create a 2 factor. There three cases (here $x$ is a vertex, or a coset):

(1) $a \cdot x = x$ this makes a loop and also a loop in the "reverse" direction since then $a^{-1} \cdot x =x$.

(2) $a \cdot a \cdot x = x$, this is an interesting case [and the main cause of my confusion], because it will often be displayed in the literature as a single-edge although there should be another edge coming from the fact that $a^{-1} \cdot a^{-1} \cdot x = x$

(3) $a$ makes a longer cycle before coming back to $x$.

If there are no loops then elements $a \in S$ so that $a = a^{-1}$ can only make a matching of the graph.

Hence, under the convention for degree taken, loopless Schreier graphs need to have a matching.

On the other hand, if you have a matching then you can label this matching by an element $b$ with $b=b^{-1}$. The rest of the graph is $2r$-regular for some $r$, so you can find $r$ disjoint $2$-factors and label them with $a_1,a_2,\ldots,a_r$.

My confusion came from diagrams such as the one below. Edge with arrows indicate how an element acts. Edge without arrow means the element switches both ends of that edge. This completely determine the action, but it gives a false impression on the vertex degree. In the picture below the vertices have degree 5 or 6 (depending on whether $c= c^{-1}$ or $c \neq c^{-1}$).