Sets of $r$-graphs that color all $r$-graphs

Abstract

An $r$-regular graph is an $r$-graph, if every odd set of vertices is connected to its complement by at least $r$ edges. Let $G$ and $H$ be $r$-graphs. An $H$-coloring of $G$ is a mapping $f:E(G)\to E(H)$ such that each $r$ adjacent edges of $G$ are mapped to $r$ adjacent edges of $H$. For every $r\ge 3$, let ${\mathcal{H}}_r$ be an inclusion-wise minimal set of connected $r$-graphs, such that for every connected $r$-graph $G$ there is an $H\in {\mathcal{H}}_r$ which colors $G$. We show that ${\mathcal{H}}_r$ is unique and characterize ${\mathcal{H}}_r$ by showing that $G\in {\mathcal{H}}_r$ if and only if the only connected $r$-graph coloring $G$ is $G$ itself. The Petersen Coloring Conjecture states that the Petersen graph $P$ colors every bridgeless cubic graph. We show that if true, this is a very exclusive situation. Indeed, either ${\mathcal{H}}_3=\{P\}$ or ${\mathcal{H}}_3$ is an infinite set and if $r\ge 4$, then ${\mathcal{H}}_r$ is an infinite set. Similar results hold for the restriction on simple $r$-graphs. By definition, $r$-graphs of class $1$ (i.e. those having edge-chromatic number equal to $r$) can be colored with any $r$-graph. Hence, our study will focus on those $r$-graphs whose edge-chromatic number is bigger than $r$, also called $r$-graphs of class $2$. We determine the set of smallest $r$-graphs of class 2 and show that it is a subset of ${\mathcal{H}}_r$.

25 pages, 7 figures