{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T15:39:50Z","timestamp":1760369990098,"version":"3.37.3"},"reference-count":63,"publisher":"EDP Sciences","issue":"3","license":[{"start":{"date-parts":[[2024,5,6]],"date-time":"2024-05-06T00:00:00Z","timestamp":1714953600000},"content-version":"vor","delay-in-days":5,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","award":["0588\/2018"],"award-info":[{"award-number":["0588\/2018"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004586","name":"Funda\u00e7\u00e3o Carlos Chagas Filho de Amparo \u00e0 Pesquisa do Estado do Rio de Janeiro","doi-asserted-by":"publisher","award":["E-26\/202.793\/2017, E-26\/203.232\/2017"],"award-info":[{"award-number":["E-26\/202.793\/2017, E-26\/203.232\/2017"]}],"id":[{"id":"10.13039\/501100004586","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["428941\/2016-8, 302823\/2016-6, 407635\/2018-1, 311545\/2018-1"],"award-info":[{"award-number":["428941\/2016-8, 302823\/2016-6, 407635\/2018-1, 311545\/2018-1"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2024,3,13]]},"published-print":{"date-parts":[[2024,5]]},"abstract":"<jats:p>An <jats:italic>r<\/jats:italic>-graph is an <jats:italic>r<\/jats:italic>-regular graph <jats:italic>G<\/jats:italic> on an even number of vertices where every odd set <jats:italic>X<\/jats:italic> \u2286 <jats:italic>V<\/jats:italic> (<jats:italic>G<\/jats:italic>) is connected by at least <jats:italic>r<\/jats:italic> edges to its complement <jats:italic>V<\/jats:italic> (<jats:italic>G<\/jats:italic>) \\ <jats:italic>X<\/jats:italic>. Every <jats:italic>r<\/jats:italic>-graph has a perfect matching and in a poorly matchable <jats:italic>r<\/jats:italic>-graph every pair of perfect matchings intersect, which implies that poorly matchable <jats:italic>r<\/jats:italic>-graphs are not <jats:italic>r<\/jats:italic>-edge-colourable. We prove, for each fixed <jats:italic>r<\/jats:italic> \u2265 3, that poorly matchable <jats:italic>r<\/jats:italic>-graph recognition is coNP-complete, an indication that, for each odd <jats:italic>d<\/jats:italic> \u2265 3, it may be a hard problem to recognise <jats:italic>d<\/jats:italic>-regular (<jats:italic>d<\/jats:italic> \u2212 1)-edge-connected non-<jats:italic>d<\/jats:italic>-edge-colourable graphs, referred to as <jats:italic>d<\/jats:italic>-snarks in this paper. We show how to construct, for every fixed odd <jats:italic>d<\/jats:italic> \u2265 5, an infinite family of <jats:italic>d<\/jats:italic>-snarks. These families provide a natural extension to the well-known Loupekine snarks. We also discuss how the hunting of the smallest <jats:italic>d<\/jats:italic>-snarks may help in strengthening and better understanding the major Overfull Conjecture on edge-colouring simple graphs.<\/jats:p>","DOI":"10.1051\/ro\/2024068","type":"journal-article","created":{"date-parts":[[2024,3,16]],"date-time":"2024-03-16T20:02:35Z","timestamp":1710619355000},"page":"2055-2073","source":"Crossref","is-referenced-by-count":1,"title":["The hardness of recognising poorly matchable graphs and the hunting of the <i>d<\/i>-snark"],"prefix":"10.1051","volume":"58","author":[{"given":"Leandro M.","family":"Zatesko","sequence":"first","affiliation":[]},{"given":"Renato","family":"Carmo","sequence":"additional","affiliation":[]},{"given":"Andr\u00e9 L.P.","family":"Guedes","sequence":"additional","affiliation":[]},{"given":"Raphael C.S.","family":"Machado","sequence":"additional","affiliation":[]},{"given":"Celina M.H.","family":"Figueiredo","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2024,5,6]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/j.jctb.2022.07.001","volume":"157","author":"Balogh","year":"2022","journal-title":"J. Comb. Theory Ser. B"},{"key":"R2","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"Bj\u00f6rklund","year":"2009","journal-title":"SIAM J. Comput."},{"key":"R3","first-page":"31","volume":"1","author":"Blanu\u0161a","year":"1946","journal-title":"Glasnik. Mat. Fiz. Astr. Ser. II"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Brinkmann G., Goedgebeur J., H\u00a8agglund J. and Markstr\u00f6m K., Generation and Properties of Snarks. Vol. 103 (2012).","DOI":"10.1016\/j.jctb.2013.05.001"},{"key":"R5","unstructured":"Brown W.G., Erd\u0151s P. and S\u00f3s V.T., Some extremal problems on r-graphs. In New Directions in the Theory of Graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich, 1971). Academic Press, New York (1973) 53\u201363."},{"key":"R6","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0166-218X(91)90010-T","volume":"30","author":"Cai","year":"1991","journal-title":"Discrete Appl. Math."},{"key":"R7","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1002\/jgt.3190080403","volume":"8","author":"Chetwynd","year":"1984","journal-title":"J. Graph Theory"},{"key":"R8","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1112\/plms\/s3-50.2.193","volume":"3","author":"Chetwynd","year":"1985","journal-title":"Proc. London Math. Soc."},{"key":"R9","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1017\/S030500410006610X","volume":"100","author":"Chetwynd","year":"1986","journal-title":"Math. Proc. Cambridge Philos. Soc."},{"key":"R10","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/S0167-5060(08)70453-9","volume":"41","author":"Chetwynd","year":"1989","journal-title":"Ann. Discrete Math."},{"key":"R11","doi-asserted-by":"crossref","first-page":"R32","DOI":"10.37236\/304","volume":"17","author":"Chladn\u00fd","year":"2010","journal-title":"Electron. J. Comb."},{"key":"R12","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.tcs.2007.07.046","volume":"389","author":"De Simone","year":"2007","journal-title":"Theor. Comput. Sci."},{"key":"R13","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1007\/s10878-009-9235-8","volume":"18","author":"De Simone","year":"2009","journal-title":"J. Comb. Optim."},{"key":"R14","doi-asserted-by":"crossref","first-page":"67","DOI":"10.2307\/3610702","volume":"32","author":"Descartes","year":"1948","journal-title":"Math. Gaz."},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Diestel R., Graph Theory, 4th edition. Springer (2010).","DOI":"10.1007\/978-3-642-14279-6"},{"key":"R16","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"Edmonds","year":"1965","journal-title":"Can. J. Math."},{"key":"R17","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69B","author":"Edmonds","year":"1965","journal-title":"J. Res. Natl. Bur. Standards B (Math. Math. Phys.)"},{"key":"R18","doi-asserted-by":"crossref","first-page":"1646","DOI":"10.1016\/j.aim.2011.03.015","volume":"227","author":"Esperet","year":"2011","journal-title":"Adv. Math."},{"key":"R19","unstructured":"Folkman J. and Fulkerson D.R., Edge colorings in bipartite graphs. Comb. Math. Appl. (1969) 561\u2013577."},{"key":"R20","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/j.ipl.2019.02.006","volume":"146","author":"Galby","year":"2019","journal-title":"Inf. Process. Lett."},{"key":"R21","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1038\/scientificamerican0476-126","volume":"4","author":"Gardner","year":"1976","journal-title":"Sci. Am."},{"key":"R22","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1016\/j.dam.2023.06.040","volume":"340","author":"Gonzaga","year":"2023","journal-title":"Discrete Appl. Math."},{"key":"R23","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1017\/S0305004100067244","volume":"102","author":"Hilton","year":"1987","journal-title":"Math. Proc. Cambridge Philos. Soc."},{"key":"R24","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1002\/jgt.3190160207","volume":"16","author":"Hoffman","year":"1992","journal-title":"J. Graph Theory"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"Holton D.A. and Sheehan J., The Petersen Graph. Cambridge University Press (1993).","DOI":"10.1017\/CBO9780511662058"},{"key":"R26","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"Holyer","year":"1981","journal-title":"SIAM J. Comput."},{"key":"R27","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1080\/00029890.1975.11993805","volume":"82","author":"Isaacs","year":"1975","journal-title":"Amer. Math. Monthly"},{"key":"R28","unstructured":"Isaacs R., Loupekine\u2019s snarks: A bifamily of non-Tait-colorable graphs, Technical Report 263, The Johns Hopkins University (1976)."},{"key":"R29","doi-asserted-by":"crossref","unstructured":"Jaeger F., A survey of the cycle double cover conjecture. In Annals of Discrete Mathematics 27 \u2013 Cycles in Graphs, Vol. 27 of North-Holland Mathematics Studies (1985) 1\u201312.","DOI":"10.1016\/S0304-0208(08)72993-1"},{"key":"R30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1098\/rstl.1886.0002","volume":"177","author":"Kempe","year":"1886","journal-title":"Philos. Trans. R. Soc."},{"key":"R31","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1006\/eujc.2001.0563","volume":"23","author":"Kochol","year":"2002","journal-title":"Eur. J. Comb."},{"key":"R32","first-page":"104","volume":"34","author":"K\u0151nig","year":"1916","journal-title":"Math. Term\u00e9szettudom\u00e1nyi \u00c9rtesito"},{"key":"R33","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/S0096-3003(96)00021-5","volume":"93","author":"Koreas","year":"1997","journal-title":"J. Appl. Math. Comput."},{"key":"R34","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0196-6774(83)90032-9","volume":"4","author":"Leven","year":"1983","journal-title":"J. Algorithms"},{"key":"R35","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0095-8956(87)90021-9","volume":"42","author":"Lov\u00e1sz","year":"1987","journal-title":"J. Comb. Theory Ser. B"},{"key":"R36","doi-asserted-by":"crossref","first-page":"1548","DOI":"10.1137\/22M1500654","volume":"37","author":"Ma","year":"2023","journal-title":"SIAM J. Discrete Math."},{"key":"R37","doi-asserted-by":"crossref","first-page":"1336","DOI":"10.1016\/j.dam.2009.01.009","volume":"158","author":"Machado","year":"2010","journal-title":"Discrete Appl. Math."},{"key":"R38","unstructured":"Meidanis J., Edge coloring of cycle powers is easy (1998). Unpublished manuscript. URL: http:\/\/www.ic.unicamp.br\/~meidanis\/research\/edge\/cpowers.ps."},{"key":"R39","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/S0095-8956(73)80006-1","volume":"14","author":"Meredith","year":"1973","journal-title":"J. Comb. Theory Ser. B"},{"key":"R40","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/0012-365X(81)90006-6","volume":"34","author":"Naddef","year":"1981","journal-title":"Discrete Math."},{"key":"R41","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/0166-218X(94)90101-5","volume":"51","author":"Niessen","year":"1994","journal-title":"Discrete Appl. Math."},{"key":"R42","doi-asserted-by":"crossref","unstructured":"Niessen T., How to find overfull subgraphs in graphs with large maximum degree, II. Electron. J. Comb. 8 (2001).","DOI":"10.37236\/1551"},{"key":"R43","unstructured":"Nishizeki T. and Kashiwagi K., An upper bound on the chromatic index of multigraphs, edited by Alavi Y., Chartrand G., Lick D.R., Wall C.E. and Lesniak L.. In: Graph Theory with Applications to Algorithms and Computer Science. Wiley, New York (1985) 595\u2013604."},{"key":"R44","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/S0166-218X(97)00128-5","volume":"82","author":"Ortiz","year":"1998","journal-title":"Discrete Appl. Math."},{"key":"R45","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1287\/moor.7.1.67","volume":"7","author":"Padberg","year":"1982","journal-title":"Math. Oper. Res."},{"key":"R46","first-page":"567","volume":"165\/166","author":"Perkovic","year":"1997","journal-title":"Discrete Appl. Math."},{"key":"R47","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/BF02392606","volume":"15","author":"Petersen","year":"1891","journal-title":"Acta Math."},{"key":"R48","first-page":"225","volume":"5","author":"Petersen","year":"1898","journal-title":"L\u2019Interm\u00e9diaire des Math\u00e9maticiens"},{"key":"R49","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1002\/jgt.3190050103","volume":"5","author":"Plantholt","year":"1981","journal-title":"J. Graph Theory"},{"key":"R50","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/(SICI)1097-0118(199909)32:1<1::AID-JGT1>3.0.CO;2-B","volume":"32","author":"Rizzi","year":"1999","journal-title":"J. Graph Theory"},{"key":"R51","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1002\/rsa.3240050209","volume":"5","author":"Robinson","year":"1994","journal-title":"Random Struct. Algor."},{"key":"R52","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1112\/plms\/s3-38.3.423","volume":"38","author":"Seymour","year":"1979","journal-title":"Proc. London Math. Soc."},{"key":"R53","unstructured":"Seymour P.D., Some unsolved problems on one-factorizations of graphs, edited by Bondy J.A. and Murty U.S.R.. In: Graph Theory and Related Topics. Academic Press, New York (1979) 367\u2013368."},{"key":"R54","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1016\/j.endm.2007.01.059","volume":"28","author":"Skupie\u0144","year":"2007","journal-title":"Electron. Notes Discrete Math."},{"key":"R55","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1017\/S0004972700042660","volume":"8","author":"Szekeres","year":"1973","journal-title":"Bull. Aust. Math. Soc."},{"key":"R56","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1017\/S0370164600044229","volume":"10","author":"Tait","year":"1880","journal-title":"Proc. R. Soc. Edinb. Sect. A"},{"key":"R57","unstructured":"Vieira \u00c9.A., Grafos d-snarks, Undergraduate thesis, Federal University of Fronteira Sul (2019)."},{"key":"R58","first-page":"25","volume":"3","author":"Vizing","year":"1964","journal-title":"Diskret. Anal."},{"key":"R59","first-page":"9","volume":"5","author":"Vizing","year":"1965","journal-title":"Diskret. Anal."},{"key":"R60","unstructured":"Zatesko L.M. and Vieira E.A., P = NP or 5-snarks exist. In Proc. 3rd Workshop de Pesquisa em Computa\u00e7\u00e3 \u00b8 o dos Campos Gerais (WPCCG \u201919). Ponta Grossa, Brazil (2019) 135\u2013140."},{"key":"R61","unstructured":"Zatesko L.M., Carmo R., Guedes A.L.P., Zorzi A., Machado R.C.S. and Figueiredo C.M.H., On the chromatic index of complementary prisms. In Proc. X European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB \u201919), Vol. 88 of Acta Math. Univ. Comenianae. Bratislava (2019) 1071\u20131077."},{"key":"R62","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1016\/j.dam.2020.03.044","volume":"281","author":"Zatesko","year":"2020","journal-title":"Discrete Appl. Math."},{"key":"R63","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/j.dam.2016.10.022","volume":"245","author":"Zorzi","year":"2018","journal-title":"Discrete Appl. Math."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024068\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,6]],"date-time":"2024-05-06T08:10:47Z","timestamp":1714983047000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024068"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5]]},"references-count":63,"journal-issue":{"issue":"3"},"alternative-id":["ro230063"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2024068","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2024,5]]}}}