{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T19:10:18Z","timestamp":1760037018605,"version":"build-2065373602"},"reference-count":21,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T00:00:00Z","timestamp":1758585600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Natural Science Foundation of China","award":["11661084","Qian Ke He Ji Chu[2017]1201","2022XRC067","2022XRC093"],"award-info":[{"award-number":["11661084","Qian Ke He Ji Chu[2017]1201","2022XRC067","2022XRC093"]}]},{"name":"Science and Technology Foundation of Guizhou province","award":["11661084","Qian Ke He Ji Chu[2017]1201","2022XRC067","2022XRC093"],"award-info":[{"award-number":["11661084","Qian Ke He Ji Chu[2017]1201","2022XRC067","2022XRC093"]}]},{"name":"Scientific Research Grants of Suqian University","award":["11661084","Qian Ke He Ji Chu[2017]1201","2022XRC067","2022XRC093"],"award-info":[{"award-number":["11661084","Qian Ke He Ji Chu[2017]1201","2022XRC067","2022XRC093"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>The famous Four-Color Conjecture (now Theorem) states that any planar graph could be colored using four colors. Hadwiger\u2019s conjecture strengthens the Four-Color Conjecture by asserting that every graph with chromatic number t contains a complete minor of order t. In this paper we investigate Hadwiger\u2019s conjecture for the complements of the Petersen graph and the Clebsch graph; both are strongly regular graphs with independence number two (hence dense graphs). We confirm Haj\u00f3s\u2019 conjecture, hence Hadwiger\u2019s conjecture, for these graphs. Moreover, we show that for each of these graphs the exact hadwiger number is strictly greater its chromatic number.<\/jats:p>","DOI":"10.3390\/sym17101588","type":"journal-article","created":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T10:27:53Z","timestamp":1758623273000},"page":"1588","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Hadwiger\u2019s Conjecture for Dense Strongly Regular Graphs"],"prefix":"10.3390","volume":"17","author":[{"given":"Guangjun","family":"Xu","sequence":"first","affiliation":[{"name":"School of Mathematics and Physics, Suqian University, Suqian 223800, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lijuan","family":"Lei","sequence":"additional","affiliation":[{"name":"School of Information and Management Sciences, Henan Agricultural University, Zhengzhou 450002, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xianghu","family":"Liu","sequence":"additional","affiliation":[{"name":"School of Mathematics and Physics, Suqian University, Suqian 223800, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yanfang","family":"Li","sequence":"additional","affiliation":[{"name":"School of Mathematics and Physics, Suqian University, Suqian 223800, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,9,23]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Bondy, J.A., and Murty, U.S.R. (2008). Graph Theory, Springer.","DOI":"10.1007\/978-1-84628-970-5"},{"key":"ref_2","first-page":"133","article-title":"\u00dcber eine Klassifikation der Streckenkomplexe","volume":"88","author":"Hadwiger","year":"1943","journal-title":"Vierteljschr. Naturforsch. Ges. Z\u00fcrich"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF01202354","article-title":"Hadwiger\u2019s conjecture for K6-free graphs","volume":"13","author":"Robertson","year":"1993","journal-title":"Combinatorica"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1152","DOI":"10.1016\/j.ejc.2006.03.002","article-title":"Hadwiger\u2019s conjecture for powers of cycles and their complements","volume":"28","author":"Li","year":"2007","journal-title":"Eur. J. Comb."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"946","DOI":"10.1016\/j.ejc.2008.07.024","article-title":"Hadwiger\u2019s conjecture for proper circular arc graphs","volume":"30","author":"Belkale","year":"2009","journal-title":"Eur. J. Comb."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1016\/j.ejc.2003.09.020","article-title":"Hadwiger\u2019s conjecture for line graphs","volume":"25","author":"Reed","year":"2004","journal-title":"Eur. J. Comb."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1002\/jgt.20321","article-title":"Hadwiger\u2019s conjecture for quasi-line graphs","volume":"59","author":"Chudnovsky","year":"2008","journal-title":"J. Graph Theory"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"P4.21","DOI":"10.37236\/5134","article-title":"Hadwiger\u2019s conjecture for 3-arc graphs","volume":"23","author":"Wood","year":"2016","journal-title":"Electron. J. Combin."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1002\/jgt.22007","article-title":"Hadwiger\u2019s conjecture for the complements of Kneser graphs","volume":"84","author":"Xu","year":"2017","journal-title":"J. Graph Theory"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/j.ejc.2018.10.003","article-title":"Hadwiger\u2019s conjecture for squares of 2-trees","volume":"76","author":"Chandran","year":"2019","journal-title":"Eur. J. Comb."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"65","DOI":"10.47443\/dml.2024.186","article-title":"A note on Hadwiger\u2019s conjecture for path-chromatic number","volume":"15","author":"Yokoi","year":"2025","journal-title":"Discrete Math. Lett."},{"key":"ref_12","first-page":"249","article-title":"A survey of Hadwiger\u2019s conjecture","volume":"115","author":"Toft","year":"1996","journal-title":"Congr. Numer."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Nash, J.F., and Rassias, M.T. (2016). Hadwiger\u2019s conjecture. Open Problems in Mathematics, Springer. [1st ed.].","DOI":"10.1007\/978-3-319-32162-2"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1016\/0095-8956(79)90062-5","article-title":"Haj\u00f3s\u2019 graph-coloring conjecture: Variations and counterexamples","volume":"26","author":"Catlin","year":"1979","journal-title":"J. Comb. Theory (Ser. B)"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/j.jctb.2004.08.005","article-title":"Some remarks on Haj\u00f3s\u2019 conjecture","volume":"93","author":"Thomassen","year":"2005","journal-title":"J. Comb. Theory (Ser. B)"},{"key":"ref_16","first-page":"733","article-title":"Hadwiger\u2019s conjecture and seagull packing","volume":"57","author":"Chudnovsky","year":"2010","journal-title":"Not. Am. Math. Soc."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"4571","DOI":"10.1109\/TIP.2021.3070188","article-title":"Petersen graph multi-orientation based multi-scale ternary pattern (PGMO-MSTP): An efficient descriptor for texture and material recognition","volume":"30","author":"Khadiri","year":"2021","journal-title":"IEEE Trans. Image Process."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Zheng, S., Cai, H., Wang, Y., and Sun, Q. (2022). On the Chromatic Index of the Signed Generalized Petersen Graph GP(n,2). Axioms, 11.","DOI":"10.3390\/axioms11080393"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Gabrov\u0161ek, B., Peperko, A., and \u017derovnik, J. (2020). Independent Rainbow Domination Numbers of Generalized Petersen Graphs P(n,2) and P(n,3). Mathematics, 8.","DOI":"10.3390\/math8060996"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1109\/TPDS.2019.2941207","article-title":"A novel low cost interconnection architecture based on the generalized hypercube","volume":"31","author":"Wang","year":"2020","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Godsil, C., and Royle, G. (2001). Algebraic Graph Theory, Springer.","DOI":"10.1007\/978-1-4613-0163-9"}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/17\/10\/1588\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T18:47:38Z","timestamp":1760035658000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/17\/10\/1588"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,23]]},"references-count":21,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2025,10]]}},"alternative-id":["sym17101588"],"URL":"https:\/\/doi.org\/10.3390\/sym17101588","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2025,9,23]]}}}