Induced Minors and Region Intersection Graphs
Bonnet, Édouard1; Hickingbotham, Robert2
1 CNRS, ENS de Lyon, Université Lyon 1, LIP, UMR 5668, 69342 Lyon Cedex 07, France
2 Université libre de Bruxelles, Département d’Informatique, Ixelles, Belgium
Innovations in Graph Theory, Volume 2 (2025), pp. 313-327

We show that for any positive integers $g$ and $t$, there is a $K_{6}^{(1)}$-induced-minor-free graph of girth at least $g$ that is not a region intersection graph over the class of $K_t$-minor-free graphs. This answers in a strong form the recently raised question of whether for every graph $H$ there is a graph $H^{\prime }$ such that $H$-induced-minor-free graphs are region intersection graphs over $H^{\prime }$-minor-free graphs.

Received:
Accepted:
Published online:
DOI: 10.5802/igt.15
Classification: 05C75, 05C62, 05C83
Keywords: Induced Minors, Region Intersection Graphs

Bonnet, Édouard 1; Hickingbotham, Robert 2

1 CNRS, ENS de Lyon, Université Lyon 1, LIP, UMR 5668, 69342 Lyon Cedex 07, France
2 Université libre de Bruxelles, Département d’Informatique, Ixelles, Belgium
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{IGT_2025__2__313_0,
     author = {Bonnet, \'Edouard and Hickingbotham, Robert},
     title = {Induced {Minors} and {Region} {Intersection} {Graphs}},
     journal = {Innovations in Graph Theory},
     pages = {313--327},
     year = {2025},
     publisher = {Stichting Innovations in Graph Theory},
     volume = {2},
     doi = {10.5802/igt.15},
     language = {en},
     url = {https://igt.centre-mersenne.org/articles/10.5802/igt.15/}
}
TY  - JOUR
AU  - Bonnet, Édouard
AU  - Hickingbotham, Robert
TI  - Induced Minors and Region Intersection Graphs
JO  - Innovations in Graph Theory
PY  - 2025
SP  - 313
EP  - 327
VL  - 2
PB  - Stichting Innovations in Graph Theory
UR  - https://igt.centre-mersenne.org/articles/10.5802/igt.15/
DO  - 10.5802/igt.15
LA  - en
ID  - IGT_2025__2__313_0
ER  - 
%0 Journal Article
%A Bonnet, Édouard
%A Hickingbotham, Robert
%T Induced Minors and Region Intersection Graphs
%J Innovations in Graph Theory
%D 2025
%P 313-327
%V 2
%I Stichting Innovations in Graph Theory
%U https://igt.centre-mersenne.org/articles/10.5802/igt.15/
%R 10.5802/igt.15
%G en
%F IGT_2025__2__313_0
Bonnet, Édouard; Hickingbotham, Robert. Induced Minors and Region Intersection Graphs. Innovations in Graph Theory, Volume 2 (2025), pp. 313-327. doi: 10.5802/igt.15

[1] Abrishami, Tara; Briański, Marcin; Davies, James; Du, Xiying; Masaříková, Jana; Rzążewski, Paweł; Walczak, Bartosz Burling graphs in graphs with large chromatic number (2025) | arXiv | Zbl

[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–17, 1990, Baltimore, Maryland, USA (Ortiz, Harriet, ed.), ACM Press (1990), pp. 293-299 | DOI

[3] Bonamy, Marthe; Bonnet, Édouard; Déprés, Hugues; Esperet, Louis; Geniet, Colin; Hilaire, Claire; Thomassé, Stéphan; Wesolek, Alexandra Sparse graphs with bounded induced cycle packing number have logarithmic treewidth, J. Comb. Theory, Ser. B, Volume 167 (2024), pp. 215-249 | DOI | Zbl | MR

[4] Bonnet, Édouard; Hodor, Jedrzej; Korhonen, Tuukka; Masařík, Tomás Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor (2023) | arXiv | DOI

[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) | arXiv | Zbl

[6] Dallard, Clément; 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 | DOI | Zbl | MR

[7] Davies, James Oberwolfach report 1/2022 (2022) (https://doi.org/10.4171/OWR/2022/1) | DOI

[8] Davies, James; Hickingbotham, Robert; Illingworth, Freddie; McCarty, Rose Fat minors cannot be thinned (by quasi-isometries) (2024) | arXiv | Zbl

[9] Dujmović, 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 | DOI | Zbl | MR

[10] Gartland, Peter Quasi-Polynomial Time Techniques for Independent Set and Beyond in Hereditary Graph Classes, Ph. D. Thesis, UC Santa Barbara (2023)

[11] Georgakopoulos, Agelos; Papasoglu, Panos Graph minors and metric spaces, Combinatorica, Volume 45 (2025), Paper no. 33, 29 pages | DOI | Zbl | MR

[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–10, 2024 (Woodruff, David P., ed.), Society for Industrial and Applied Mathematics (2024), pp. 5249-5275 | DOI | Zbl | MR

[13] Lee, James R. Separators in region intersection graphs, Proceedings of the 8th Innovations in Theoretical Computer Science Conference (Papadimitriou, Christos H., ed.) (LIPIcs – Leibniz International Proceedings in Informatics), Volume 67, Schloss Dagstuhl, 2017 (Article 1, 8 p.) | DOI | Zbl

[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 | DOI | Zbl | MR

[15] Lokshtanov, Daniel Personal communication, 2025

[16] McCarty, Rose Structurally Sparse Graphs (2023) (Lecture series at the Structural Graph Theory Bootcamp, Warsaw, https://sites.google.com/view/strug/main)

[17] Pohoata, Andrei Cosmin Unavoidable induced subgraphs of large graphs, Senior Theses, Department of Mathematics, Princeton University (2014) http://arks.princeton.edu/...

[18] Robertson, Neil; Seymour, Paul D. Graph Minors I–XXIII, J. Combin. Theory, Ser. B & J. Algorithms (1983–2012)

[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 | DOI | MR | Zbl

[20] Sinden, Frank W. Topology of thin film RC circuits, Bell Syst. Tech. J., Volume 45 (1966) no. 9, pp. 1639-1662 | DOI | Zbl

[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)

Cited by Sources: