---
_id: '59169'
abstract:
- lang: eng
  text: 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 such that each r adjacent edges of G are mapped to r adjacent
    edges of H. For every , let be an inclusion-wise minimal set of connected r-graphs,
    such that for every connected r-graph G there is an which colors G. The Petersen
    Coloring Conjecture states that consists of the Petersen graph P. We show that
    if true, then this is a very exclusive situation. Our main result is that either
    or is an infinite set and if , then is an infinite set. In particular, for all
    , is unique. We first characterize and then prove that if contains more than one
    element, then it is an infinite set. To obtain our main result we show that 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.
article_number: '16'
author:
- first_name: Yulai
  full_name: Ma, Yulai
  last_name: Ma
- first_name: Davide
  full_name: Mattiolo, Davide
  last_name: Mattiolo
- first_name: Eckhard
  full_name: Steffen, Eckhard
  id: '15548'
  last_name: Steffen
  orcid: 0000-0002-9808-7401
- first_name: Isaak H.
  full_name: Wolf, Isaak H.
  last_name: Wolf
citation:
  ama: Ma Y, Mattiolo D, Steffen E, Wolf IH. Sets of r-Graphs that Color All r-Graphs.
    <i>Combinatorica</i>. 2025;45(2). doi:<a href="https://doi.org/10.1007/s00493-025-00144-4">10.1007/s00493-025-00144-4</a>
  apa: Ma, Y., Mattiolo, D., Steffen, E., &#38; Wolf, I. H. (2025). Sets of r-Graphs
    that Color All r-Graphs. <i>Combinatorica</i>, <i>45</i>(2), Article 16. <a href="https://doi.org/10.1007/s00493-025-00144-4">https://doi.org/10.1007/s00493-025-00144-4</a>
  bibtex: '@article{Ma_Mattiolo_Steffen_Wolf_2025, title={Sets of r-Graphs that Color
    All r-Graphs}, volume={45}, DOI={<a href="https://doi.org/10.1007/s00493-025-00144-4">10.1007/s00493-025-00144-4</a>},
    number={216}, journal={Combinatorica}, publisher={Springer Science and Business
    Media LLC}, author={Ma, Yulai and Mattiolo, Davide and Steffen, Eckhard and Wolf,
    Isaak H.}, year={2025} }'
  chicago: Ma, Yulai, Davide Mattiolo, Eckhard Steffen, and Isaak H. Wolf. “Sets of
    R-Graphs That Color All r-Graphs.” <i>Combinatorica</i> 45, no. 2 (2025). <a href="https://doi.org/10.1007/s00493-025-00144-4">https://doi.org/10.1007/s00493-025-00144-4</a>.
  ieee: 'Y. Ma, D. Mattiolo, E. Steffen, and I. H. Wolf, “Sets of r-Graphs that Color
    All r-Graphs,” <i>Combinatorica</i>, vol. 45, no. 2, Art. no. 16, 2025, doi: <a
    href="https://doi.org/10.1007/s00493-025-00144-4">10.1007/s00493-025-00144-4</a>.'
  mla: Ma, Yulai, et al. “Sets of R-Graphs That Color All r-Graphs.” <i>Combinatorica</i>,
    vol. 45, no. 2, 16, Springer Science and Business Media LLC, 2025, doi:<a href="https://doi.org/10.1007/s00493-025-00144-4">10.1007/s00493-025-00144-4</a>.
  short: Y. Ma, D. Mattiolo, E. Steffen, I.H. Wolf, Combinatorica 45 (2025).
date_created: 2025-03-27T09:46:34Z
date_updated: 2025-03-27T09:48:48Z
department:
- _id: '542'
doi: 10.1007/s00493-025-00144-4
intvolume: '        45'
issue: '2'
language:
- iso: eng
publication: Combinatorica
publication_identifier:
  issn:
  - 0209-9683
  - 1439-6912
publication_status: published
publisher: Springer Science and Business Media LLC
status: public
title: Sets of r-Graphs that Color All r-Graphs
type: journal_article
user_id: '15540'
volume: 45
year: '2025'
...
---
_id: '49905'
abstract:
- lang: eng
  text: "For 0 ≤ t ≤ r let m(t, r) be the maximum number s such that every t-edge-connected
    r-graph has s pairwise disjoint perfect matchings. There are only a few values
    of m(t, r) known, for instance m(3, 3) = m(4, r) = 1, and m(t, r) ≤ r − 2 for
    all t \x03 = 5,\r\nand m(t, r) ≤ r − 3 if r is even. We prove that m(2l, r) ≤
    3l − 6 for every l ≥ 3 and r ≥ 2l."
author:
- first_name: Yulai
  full_name: Ma, Yulai
  id: '92748'
  last_name: Ma
- first_name: Davide
  full_name: Mattiolo, Davide
  last_name: Mattiolo
- first_name: Eckhard
  full_name: Steffen, Eckhard
  id: '15548'
  last_name: Steffen
  orcid: 0000-0002-9808-7401
- first_name: Isaak Hieronymus
  full_name: Wolf, Isaak Hieronymus
  id: '88145'
  last_name: Wolf
citation:
  ama: Ma Y, Mattiolo D, Steffen E, Wolf IH. Edge-Connectivity and Pairwise Disjoint
    Perfect Matchings in Regular Graphs. <i>Combinatorica</i>. 2024;44:429-440. doi:<a
    href="https://doi.org/10.1007/s00493-023-00078-9">10.1007/s00493-023-00078-9</a>
  apa: Ma, Y., Mattiolo, D., Steffen, E., &#38; Wolf, I. H. (2024). Edge-Connectivity
    and Pairwise Disjoint Perfect Matchings in Regular Graphs. <i>Combinatorica</i>,
    <i>44</i>, 429–440. <a href="https://doi.org/10.1007/s00493-023-00078-9">https://doi.org/10.1007/s00493-023-00078-9</a>
  bibtex: '@article{Ma_Mattiolo_Steffen_Wolf_2024, title={Edge-Connectivity and Pairwise
    Disjoint Perfect Matchings in Regular Graphs}, volume={44}, DOI={<a href="https://doi.org/10.1007/s00493-023-00078-9">10.1007/s00493-023-00078-9</a>},
    journal={Combinatorica}, publisher={Springer Science and Business Media LLC},
    author={Ma, Yulai and Mattiolo, Davide and Steffen, Eckhard and Wolf, Isaak Hieronymus},
    year={2024}, pages={429–440} }'
  chicago: 'Ma, Yulai, Davide Mattiolo, Eckhard Steffen, and Isaak Hieronymus Wolf.
    “Edge-Connectivity and Pairwise Disjoint Perfect Matchings in Regular Graphs.”
    <i>Combinatorica</i> 44 (2024): 429–40. <a href="https://doi.org/10.1007/s00493-023-00078-9">https://doi.org/10.1007/s00493-023-00078-9</a>.'
  ieee: 'Y. Ma, D. Mattiolo, E. Steffen, and I. H. Wolf, “Edge-Connectivity and Pairwise
    Disjoint Perfect Matchings in Regular Graphs,” <i>Combinatorica</i>, vol. 44,
    pp. 429–440, 2024, doi: <a href="https://doi.org/10.1007/s00493-023-00078-9">10.1007/s00493-023-00078-9</a>.'
  mla: Ma, Yulai, et al. “Edge-Connectivity and Pairwise Disjoint Perfect Matchings
    in Regular Graphs.” <i>Combinatorica</i>, vol. 44, Springer Science and Business
    Media LLC, 2024, pp. 429–40, doi:<a href="https://doi.org/10.1007/s00493-023-00078-9">10.1007/s00493-023-00078-9</a>.
  short: Y. Ma, D. Mattiolo, E. Steffen, I.H. Wolf, Combinatorica 44 (2024) 429–440.
date_created: 2023-12-20T10:31:27Z
date_updated: 2024-03-22T12:11:35Z
department:
- _id: '542'
doi: 10.1007/s00493-023-00078-9
intvolume: '        44'
keyword:
- Computational Mathematics
- Discrete Mathematics and Combinatorics
language:
- iso: eng
page: 429-440
publication: Combinatorica
publication_identifier:
  issn:
  - 0209-9683
  - 1439-6912
publication_status: published
publisher: Springer Science and Business Media LLC
status: public
title: Edge-Connectivity and Pairwise Disjoint Perfect Matchings in Regular Graphs
type: journal_article
user_id: '15540'
volume: 44
year: '2024'
...