Combinatorica Вычислительная математика

Sets of r-Graphs that Color All r-Graphs

Yulai Ma, Davide Mattiolo, Eckhard Steffen, Isaak H. Wolf
Springer Nature · 2025-03-14 · DOI 10.1007/s00493-025-00144-4

Аннотация

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) \rightarrow E(H)$$ f : E ( G ) → E ( H ) such that each r adjacent edges of G are mapped to r adjacent edges of H . For every $$r\ge 3$$ r ≥ 3 , let $$\mathcal H_r$$ 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$$ H ∈ H r which colors G . The Petersen Coloring Conjecture states that $$\mathcal H_3$$ H 3 consists of the Petersen graph P . We show that if true, then this is a very exclusive situation. Our main result is that either $$\mathcal H_3 = \{P\}$$ H 3 = { P } or $$\mathcal H_3$$ H 3 is an infinite set and if $$r \ge 4$$ r ≥ 4 , then $$\mathcal H_r$$ H r is an infinite set. In particular, for all $$r \ge 3$$ r ≥ 3 , $$\mathcal H_r$$ H r is unique. We first characterize $$\mathcal H_r$$ H r and then prove that if $$\mathcal H_r$$ H r contains more than one element, then it is an infinite set. To obtain our main result we show that $$\mathcal H_r$$ H r contains the smallest r -graphs of class 2 and the smallest poorly matchable r -graphs, and we determine the smallest r -graphs of class 2.

Читать у издателя →