{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T20:36:14Z","timestamp":1768336574338,"version":"3.49.0"},"reference-count":21,"publisher":"MathDoc\/Centre Mersenne","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"\n We show that for any positive integers\n \n g<\/mml:mi>\n <\/mml:math>\n and\n \n t<\/mml:mi>\n <\/mml:math>\n , there is a\u00a0\n \n \n K<\/mml:mi>\n \n 6<\/mml:mn>\n <\/mml:mrow>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msubsup>\n <\/mml:math>\n -induced-minor-free graph of girth at least\u00a0\n \n g<\/mml:mi>\n <\/mml:math>\n that is not a\u00a0region intersection graph over the class of\n \n \n K<\/mml:mi>\n t<\/mml:mi>\n <\/mml:msub>\n <\/mml:math>\n -minor-free graphs. This answers in a\u00a0strong form the recently raised question of whether for every graph\u00a0\n \n H<\/mml:mi>\n <\/mml:math>\n there is a\u00a0graph\n \n \n H<\/mml:mi>\n \u2032<\/mml:mi>\n <\/mml:msup>\n <\/mml:math>\n such that\n \n H<\/mml:mi>\n <\/mml:math>\n -induced-minor-free graphs are region intersection graphs over\n \n \n H<\/mml:mi>\n \u2032<\/mml:mi>\n <\/mml:msup>\n <\/mml:math>\n -minor-free graphs.\n <\/jats:p>","DOI":"10.5802\/igt.15","type":"journal-article","created":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T15:55:41Z","timestamp":1765554941000},"page":"313-327","source":"Crossref","is-referenced-by-count":0,"title":["Induced Minors and Region Intersection Graphs"],"prefix":"10.5802","volume":"2","author":[{"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[{"name":"CNRS, ENS de Lyon, Universit\u00e9 Lyon 1, LIP, UMR 5668, 69342 Lyon Cedex 07, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Hickingbotham","sequence":"additional","affiliation":[{"name":"Universit\u00e9 libre de Bruxelles, D\u00e9partement d\u2019Informatique, Ixelles, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"3842","published-online":{"date-parts":[[2025,12,12]]},"reference":[{"key":"key2025121216553588861_1","author":"Abrishami, Tara","year":"2025","unstructured":"[1] Abrishami, Tara; Bria\u0144ski, Marcin; Davies, James; Du, Xiying; Masa\u0159\u00edkov\u00e1, Jana; Rz\u0105\u017cewski, Pawe\u0142; Walczak, Bartosz Burling graphs in graphs with large chromatic number (2025)","journal-title":"Burling graphs in graphs with large chromatic number"},{"key":"key2025121216553588861_2","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1145\/100216.100254","article-title":"A Separator Theorem for Graphs with an Excluded Minor and its Applications","author":"Alon, Noga","year":"1990","unstructured":"[2] Alon, Noga; Seymour, Paul D.; Thomas, Robin A Separator Theorem for Graphs with an Excluded Minor and its Applications, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13\u201317, 1990, Baltimore, Maryland, USA (Ortiz, Harriet, ed.), ACM Press (1990), pp. 293-299","journal-title":"Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13\u201317, 1990, Baltimore, Maryland, USA"},{"key":"key2025121216553588861_3","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/j.jctb.2024.03.003","article-title":"Sparse graphs with bounded induced cycle packing number have logarithmic treewidth","volume":"167","author":"Bonamy, Marthe","year":"2024","unstructured":"[3] Bonamy, Marthe; Bonnet, \u00c9douard; D\u00e9pr\u00e9s, Hugues; Esperet, Louis; Geniet, Colin; Hilaire, Claire; Thomass\u00e9, St\u00e9phan; Wesolek, Alexandra Sparse graphs with bounded induced cycle packing number have logarithmic treewidth, J. Comb. Theory, Ser. B, Volume 167 (2024), pp. 215-249","journal-title":"J. Comb. Theory, Ser. B"},{"key":"key2025121216553588861_4","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2312.07962","author":"Bonnet, \u00c9douard","year":"2023","unstructured":"[4] Bonnet, \u00c9douard; Hodor, Jedrzej; Korhonen, Tuukka; Masa\u0159\u00edk, Tom\u00e1s Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor (2023)","journal-title":"Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor"},{"key":"key2025121216553588861_5","author":"Campbell, Rutger","year":"2024","unstructured":"[5] Campbell, Rutger; Davies, James; Distel, Marc; Frederickson, Bryce; Gollin, J. Pascal; Hendrey, Kevin; Hickingbotham, Robert; Wiederrecht, Sebastian; Wood, David R.; Yepremyan, Liana Treewidth, Hadwiger Number, and Induced Minors (2024)","journal-title":"Treewidth, Hadwiger Number, and Induced Minors"},{"key":"key2025121216553588861_6","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1016\/J.JCTB.2024.03.005","article-title":"Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure","volume":"167","author":"Dallard, Cl\u00e9ment","year":"2024","unstructured":"[6] Dallard, Cl\u00e9ment; Milanic, Martin; Storgel, Kenny Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure, J. Comb. Theory, Ser. B, Volume 167 (2024), pp. 338-391","journal-title":"J. Comb. Theory, Ser. B"},{"key":"key2025121216553588861_7","doi-asserted-by":"publisher","DOI":"10.4171\/OWR\/2022\/1","author":"Davies, James","year":"2022","unstructured":"[7] Davies, James Oberwolfach report 1\/2022 (2022) (https:\/\/doi.org\/10.4171\/OWR\/2022\/1)","journal-title":"Oberwolfach report 1\/2022"},{"key":"key2025121216553588861_8","author":"Davies, James","year":"2024","unstructured":"[8] Davies, James; Hickingbotham, Robert; Illingworth, Freddie; McCarty, Rose Fat minors cannot be thinned (by quasi-isometries) (2024)","journal-title":"Fat minors cannot be thinned (by quasi-isometries)"},{"key":"key2025121216553588861_9","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.jctb.2017.05.006","article-title":"Layered separators in minor-closed graph classes with applications","volume":"127","author":"Dujmovi\u0107, Vida","year":"2017","unstructured":"[9] Dujmovi\u0107, Vida; Morin, Pat; Wood, David R. Layered separators in minor-closed graph classes with applications, J. Comb. Theory, Ser. B, Volume 127 (2017), pp. 111-147","journal-title":"J. Comb. Theory, Ser. B"},{"key":"key2025121216553588861_10","author":"Gartland, Peter","year":"2023","unstructured":"[10] Gartland, Peter Quasi-Polynomial Time Techniques for Independent Set and Beyond in Hereditary Graph Classes, Ph. D. Thesis, UC Santa Barbara (2023)","journal-title":"Quasi-Polynomial Time Techniques for Independent Set and Beyond in Hereditary Graph Classes"},{"key":"key2025121216553588861_11","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-025-00150-6","article-title":"Graph minors and metric spaces","volume":"45","author":"Georgakopoulos, Agelos","year":"2025","unstructured":"[11] Georgakopoulos, Agelos; Papasoglu, Panos Graph minors and metric spaces, Combinatorica, Volume 45 (2025), 33, 29 pages","journal-title":"Combinatorica"},{"key":"key2025121216553588861_12","doi-asserted-by":"publisher","first-page":"5249","DOI":"10.1137\/1.9781611977912.188","article-title":"Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition","author":"Korhonen, Tuukka","year":"2024","unstructured":"[12] Korhonen, Tuukka; Lokshtanov, Daniel Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7\u201310, 2024 (Woodruff, David P., ed.), Society for Industrial and Applied Mathematics (2024), pp. 5249-5275","journal-title":"Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7\u201310, 2024"},{"key":"key2025121216553588861_13","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2017.1","article-title":"Separators in region intersection graphs","volume":"67","author":"Lee, James R.","year":"2017","unstructured":"[13] Lee, James R. Separators in region intersection graphs, Proceedings of the 8th Innovations in Theoretical Computer Science Conference (Papadimitriou, Christos H., ed.) (LIPIcs \u2013 Leibniz International Proceedings in Informatics), Volume 67, Schloss Dagstuhl, 2017 (Article 1, 8 p.)","journal-title":"Proceedings of the 8th Innovations in Theoretical Computer Science Conference"},{"issue":"2","key":"key2025121216553588861_14","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","article-title":"A separator theorem for planar graphs","volume":"36","author":"Lipton, Richard J","year":"1979","unstructured":"[14] Lipton, Richard J; Tarjan, Robert Endre A separator theorem for planar graphs, SIAM J. Appl. Math., Volume 36 (1979) no. 2, pp. 177-189","journal-title":"SIAM J. Appl. Math."},{"key":"key2025121216553588861_15","article-title":"Personal communication","author":"Lokshtanov, Daniel","year":"2025","unstructured":"[15] Lokshtanov, Daniel Personal communication, 2025"},{"key":"key2025121216553588861_16","author":"McCarty, Rose","year":"2023","unstructured":"[16] McCarty, Rose Structurally Sparse Graphs (2023) (Lecture series at the Structural Graph Theory Bootcamp, Warsaw, https:\/\/sites.google.com\/view\/strug\/main)","journal-title":"Structurally Sparse Graphs"},{"key":"key2025121216553588861_17","author":"Pohoata, Andrei Cosmin","year":"2014","unstructured":"[17] Pohoata, Andrei Cosmin Unavoidable induced subgraphs of large graphs, Senior Theses, Department of Mathematics, Princeton University (2014) http:\/\/arks.princeton.edu\/...","journal-title":"Unavoidable induced subgraphs of large graphs"},{"key":"key2025121216553588861_18","doi-asserted-by":"crossref","DOI":"10.1016\/0095-8956(83)90079-5","article-title":"Graph Minors I\u2013XXIII","author":"Robertson, Neil","year":"1983\u20132012","unstructured":"[18] Robertson, Neil; Seymour, Paul D. Graph Minors I\u2013XXIII, J. Combin. Theory, Ser. B & J. Algorithms (1983\u20132012)","journal-title":"J. Combin. Theory, Ser. B & J. Algorithms"},{"issue":"1","key":"key2025121216553588861_19","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0095-8956(03)00042-X","article-title":"Graph minors. XVI. Excluding a non-planar graph","volume":"89","author":"Robertson, Neil","year":"2003","unstructured":"[19] Robertson, Neil; Seymour, Paul D. Graph minors. XVI. Excluding a non-planar graph, J. Comb. Theory, Ser. B, Volume 89 (2003) no. 1, pp. 43-76","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"9","key":"key2025121216553588861_20","doi-asserted-by":"publisher","first-page":"1639","DOI":"10.1002\/j.1538-7305.1966.tb01713.x","article-title":"Topology of thin film RC circuits","volume":"45","author":"Sinden, Frank W.","year":"1966","unstructured":"[20] Sinden, Frank W. Topology of thin film RC circuits, Bell Syst. Tech. J., Volume 45 (1966) no. 9, pp. 1639-1662","journal-title":"Bell Syst. Tech. J."},{"key":"key2025121216553588861_21","article-title":"Graph searching in RIGs","author":"Wiederrecht, Sebastian","year":"2023","unstructured":"[21] Wiederrecht, Sebastian Graph searching in RIGs, Open Problems, GRASTA 2023 Workshop (2023) (Section 1.3, Problem 3: https:\/\/www-sop.inria.fr\/teams\/coati\/events\/grasta2023\/slides\/Grasta23_OpenProblems.pdf)","journal-title":"Open Problems, GRASTA 2023 Workshop"}],"container-title":["Innovations in Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/igt.centre-mersenne.org\/item\/10.5802\/igt.15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T15:55:42Z","timestamp":1765554942000},"score":1,"resource":{"primary":{"URL":"https:\/\/igt.centre-mersenne.org\/articles\/10.5802\/igt.15\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,12]]},"references-count":21,"alternative-id":["10.5802\/igt.15"],"URL":"https:\/\/doi.org\/10.5802\/igt.15","relation":{},"ISSN":["3050-743X"],"issn-type":[{"value":"3050-743X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,12]]}}}