{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,7]],"date-time":"2025-05-07T04:15:00Z","timestamp":1746591300896,"version":"3.40.5"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,3,14]],"date-time":"2025-03-14T00:00:00Z","timestamp":1741910400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,3,14]],"date-time":"2025-03-14T00:00:00Z","timestamp":1741910400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100008007","name":"Universit\u00e4t Paderborn","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008007","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2025,4]]},"abstract":"Abstract<\/jats:title>\n An r<\/jats:italic>-regular graph is an r<\/jats:italic>-graph, if every odd set of vertices is connected to its complement by at least r<\/jats:italic> edges. Let G<\/jats:italic> and H<\/jats:italic> be r<\/jats:italic>-graphs. An H<\/jats:italic>\n -coloring<\/jats:italic> of G<\/jats:italic> is a mapping \n \n $$f:E(G) \\rightarrow E(H)$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n :<\/mml:mo>\n E<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n \u2192<\/mml:mo>\n E<\/mml:mi>\n (<\/mml:mo>\n H<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> such that each r<\/jats:italic> adjacent edges of G<\/jats:italic> are mapped to r<\/jats:italic> adjacent edges of H<\/jats:italic>. For every \n \n $$r\\ge 3$$<\/jats:tex-math>\n \n \n r<\/mml:mi>\n \u2265<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, let \n \n $$\\mathcal H_r$$<\/jats:tex-math>\n \n \n H<\/mml:mi>\n r<\/mml:mi>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> be an inclusion-wise minimal set of connected r<\/jats:italic>-graphs, such that for every connected r<\/jats:italic>-graph G<\/jats:italic> there is an \n \n $$H \\in \\mathcal H_r$$<\/jats:tex-math>\n \n \n H<\/mml:mi>\n \u2208<\/mml:mo>\n \n H<\/mml:mi>\n r<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> which colors G<\/jats:italic>. The Petersen Coloring Conjecture states that \n \n $$\\mathcal H_3$$<\/jats:tex-math>\n \n \n H<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> consists of the Petersen graph P<\/jats:italic>. We show that if true, then this is a very exclusive situation. Our main result is that either \n \n $$\\mathcal H_3 = \\{P\\}$$<\/jats:tex-math>\n \n \n \n H<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msub>\n =<\/mml:mo>\n \n {<\/mml:mo>\n P<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> or \n \n $$\\mathcal H_3$$<\/jats:tex-math>\n \n \n H<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is an infinite set and if \n \n $$r \\ge 4$$<\/jats:tex-math>\n \n \n r<\/mml:mi>\n \u2265<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, then \n \n $$\\mathcal H_r$$<\/jats:tex-math>\n \n \n H<\/mml:mi>\n r<\/mml:mi>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is an infinite set. In particular, for all \n \n $$r \\ge 3$$<\/jats:tex-math>\n \n \n r<\/mml:mi>\n \u2265<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, \n \n $$\\mathcal H_r$$<\/jats:tex-math>\n \n \n H<\/mml:mi>\n r<\/mml:mi>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is unique. We first characterize \n \n $$\\mathcal H_r$$<\/jats:tex-math>\n \n \n H<\/mml:mi>\n r<\/mml:mi>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> and then prove that if \n \n $$\\mathcal H_r$$<\/jats:tex-math>\n \n \n H<\/mml:mi>\n r<\/mml:mi>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> contains more than one element, then it is an infinite set. To obtain our main result we show that \n \n $$\\mathcal H_r$$<\/jats:tex-math>\n \n \n H<\/mml:mi>\n r<\/mml:mi>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> contains the smallest r<\/jats:italic>-graphs of class 2 and the smallest poorly matchable r<\/jats:italic>-graphs, and we determine the smallest r<\/jats:italic>-graphs of class 2.<\/jats:p>","DOI":"10.1007\/s00493-025-00144-4","type":"journal-article","created":{"date-parts":[[2025,3,14]],"date-time":"2025-03-14T12:22:15Z","timestamp":1741954935000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Sets of r-Graphs that Color All r-Graphs"],"prefix":"10.1007","volume":"45","author":[{"given":"Yulai","family":"Ma","sequence":"first","affiliation":[]},{"given":"Davide","family":"Mattiolo","sequence":"additional","affiliation":[]},{"given":"Eckhard","family":"Steffen","sequence":"additional","affiliation":[]},{"given":"Isaak H.","family":"Wolf","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,3,14]]},"reference":[{"unstructured":"Babai, L.: Automorphism groups, isomorphism, reconstruction. In: Handbook of Combinatorics, vols. 1, 2, pp. 1447\u20131540. Elsevier, Amsterdam (1995)","key":"144_CR1"},{"key":"144_CR2","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S1385-7258(78)80007-9","volume":"40","author":"C Berge","year":"1978","unstructured":"Berge, C., Las Vergnas, M.: On the existence of subgraphs with degree constrains. Nederl. Akad. Wetensch. Indag. Math. 40, 165\u2013176 (1978)","journal-title":"Nederl. Akad. Wetensch. Indag. Math."},{"doi-asserted-by":"crossref","unstructured":"DeVos, M., Ne\u0161et\u0159il, J., Raspaud, A.: On edge-maps whose inverse preserves flows or tensions. In: Graph Theory in Paris. Trends in Mathematics, pp. 109\u2013138. Birkh\u00e4user, Basel (2007)","key":"144_CR3","DOI":"10.1007\/978-3-7643-7400-6_10"},{"issue":"1","key":"144_CR4","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/BF01584085","volume":"1","author":"DR Fulkerson","year":"1971","unstructured":"Fulkerson, D.R.: Blocking and anti-blocking pairs of polyhedra. Math. Program. 1(1), 168\u2013194 (1971)","journal-title":"Math. Program."},{"key":"144_CR5","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1002\/(SICI)1097-0118(199901)30:1<27::AID-JGT4>3.0.CO;2-Z","volume":"30","author":"S Gr\u00fcnewald","year":"1999","unstructured":"Gr\u00fcnewald, S., Steffen, E.: Chromatic-index-critical graphs of even order. J. Graph Theory 30, 27\u201336 (1999)","journal-title":"J. Graph Theory"},{"issue":"1","key":"144_CR6","doi-asserted-by":"publisher","first-page":"161","DOI":"10.26493\/1855-3974.288.11a","volume":"7","author":"J H\u00e4gglund","year":"2014","unstructured":"H\u00e4gglund, J., Steffen, E.: Petersen-colorings and some families of snarks. Ars Math. Contemp. 7(1), 161\u2013173 (2014)","journal-title":"Ars Math. Contemp."},{"key":"144_CR7","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0167-5060(08)70861-6","volume":"8","author":"F Jaeger","year":"1980","unstructured":"Jaeger, F.: On graphic-minimal spaces. Ann. Discrete Math. 8, 123\u2013126 (1980)","journal-title":"Ann. Discrete Math."},{"unstructured":"Jaeger, F.: On five-edge-colorings of cubic graphs and nowhere-zero flow problems. Ars Combin. 20(B), 229\u2013244 (1985)","key":"144_CR8"},{"unstructured":"Jaeger, F.: Nowhere-zero flow problems. In: Selected Topics in Graph Theory, vol. 3, pp. 71\u201395. Academic Press, San Diego (1988)","key":"144_CR9"},{"unstructured":"Jin, L.: Covers and cores of $$r$$-graphs. PhD thesis, Faculty of Computer Science, Electrical Engineering and Mathematics, Paderborn University (2017)","key":"144_CR10"},{"doi-asserted-by":"crossref","unstructured":"Jin, L., Kang, Y.: Partially normal 5-edge-colorings of cubic graphs. Eur. J. Combin. 95, Paper No. 103327, 14 (2021)","key":"144_CR11","DOI":"10.1016\/j.ejc.2021.103327"},{"issue":"3","key":"144_CR12","doi-asserted-by":"publisher","first-page":"1548","DOI":"10.1137\/22M1500654","volume":"37","author":"Y Ma","year":"2023","unstructured":"Ma, Y., Mattiolo, D., Steffen, E., Wolf, I.H.: Pairwise disjoint perfect matchings in $$r$$-edge-connected $$r$$-regular graphs. SIAM J. Discret. Math. 37(3), 1548\u20131565 (2023)","journal-title":"SIAM J. Discret. Math."},{"key":"144_CR13","volume-title":"Invitation to Discrete Mathematics","author":"J Matou\u0161ek","year":"2009","unstructured":"Matou\u0161ek, J., Ne\u0161et\u0159il, J.: Invitation to Discrete Mathematics, 2nd edn. Oxford University Press, Oxford (2009)","edition":"2"},{"issue":"1","key":"144_CR14","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1002\/jgt.22507","volume":"94","author":"G Mazzuoccolo","year":"2020","unstructured":"Mazzuoccolo, G., Mkrtchyan, V.V.: Normal edge-colorings of cubic graphs. J. Graph Theory 94(1), 75\u201391 (2020)","journal-title":"J. Graph Theory"},{"key":"144_CR15","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1016\/j.dam.2023.05.006","volume":"337","author":"G Mazzuoccolo","year":"2023","unstructured":"Mazzuoccolo, G., Tabarelli, G., Zerafa, J.P.: On the existence of graphs which can colour every regular graph. Discret. Appl. Math. 337, 246\u2013256 (2023)","journal-title":"Discret. Appl. Math."},{"key":"144_CR16","first-page":"145","volume":"56","author":"VV Mkrtchyan","year":"2013","unstructured":"Mkrtchyan, V.V.: A remark on the Petersen coloring conjecture of Jaeger. Australas. J. Combin. 56, 145\u2013151 (2013)","journal-title":"Australas. J. Combin."},{"doi-asserted-by":"crossref","unstructured":"Pirot, F., Sereni, J.-S., \u0160krekovski, R.: Variations on the Petersen colouring conjecture. Electron. J. Combin. 27(1), Paper No. 1.8, 14 (2020)","key":"144_CR17","DOI":"10.37236\/8515"},{"issue":"1","key":"144_CR18","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/BF01588228","volume":"17","author":"WR Pulleyblank","year":"1979","unstructured":"Pulleyblank, W.R.: Minimum node covers and $$2$$-bicritical graphs. Math. Program. 17(1), 91\u2013103 (1979)","journal-title":"Math. Program."},{"issue":"1","key":"144_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/(SICI)1097-0118(199909)32:1<1::AID-JGT1>3.0.CO;2-B","volume":"32","author":"R Rizzi","year":"1999","unstructured":"Rizzi, R.: Indecomposable $$r$$-graphs and some other counterexamples. J. Graph Theory 32(1), 1\u201315 (1999)","journal-title":"J. Graph Theory"},{"issue":"1","key":"144_CR20","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1002\/jgt.22047","volume":"85","author":"R \u0160\u00e1mal","year":"2017","unstructured":"\u0160\u00e1mal, R.: Cycle-continuous mappings\u2013order structure. J. Graph Theory 85(1), 56\u201373 (2017)","journal-title":"J. Graph Theory"},{"doi-asserted-by":"crossref","unstructured":"Seymour, P.D.: On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte. Proc. Lond. Math. Soc. (3), 38(3), 423\u2013460 (1979)","key":"144_CR21","DOI":"10.1112\/plms\/s3-38.3.423"},{"unstructured":"Zhang, C.-Q.: Integer Flows and Cycle Covers of Graphs. Monographs and Textbooks in Pure and Applied Mathematics, vol. 205. Marcel Dekker Inc, New York (1997)","key":"144_CR22"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00144-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-025-00144-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00144-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,6]],"date-time":"2025-05-06T09:17:18Z","timestamp":1746523038000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-025-00144-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,14]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,4]]}},"alternative-id":["144"],"URL":"https:\/\/doi.org\/10.1007\/s00493-025-00144-4","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[2025,3,14]]},"assertion":[{"value":"25 September 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 January 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 March 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"16"}}