Sets of r-graphs that color all r-graphs

arXiv2305.08619MaRDI QIDQ6436636FDOQ6436636

Authors: Yulai Ma, Davide Mattiolo, Eckhard Steffen, Isaak H. Wolf 

Publication date: 15 May 2023

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 $fcolonE(G)oE(H)$ such that each $r$ adjacent edges of $G$ are mapped to $r$ adjacent edges of $H$. For every $rgeq3$, 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 $Hinmathcal{H}_r$ which colors $G$. We show that $mathcal{H}_r$ is unique and characterize $mathcal{H}_r$ by showing that $Ginmathcal{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 $rgeq4$, 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$.

This page was built for publication: Sets of $r$-graphs that color all $r$-graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6436636)