Treewidth versus clique number: induced minors

Claire Hilaire, Martin Milanič, Nicolas Trotignon, Djordje Vasić

Type: Preprint

Publication Date: 2024-10-23

Citations: 0

DOI: https://doi.org/10.48550/arxiv.2410.17979

View Chat PDF

Abstract

We prove that a hereditary class of graphs is $(\mathsf{tw}, \omega)$-bounded if and only if the induced minors of the graphs from the class form a $(\mathsf{tw}, \omega)$-bounded class.

Locations

arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Treewidth versus clique number in graph classes with a forbidden structure	2020	Clément Dallard Martin Milanič Kenny Štorgel
+ PDF Chat	Induced Minor Free Graphs: Isomorphism and Clique-Width	2016	Rémy Belmonte Yota Otachi Pascal Schweitzer
+	Induced subgraphs and path decompositions	2022	Robert Hickingbotham
+ PDF Chat	Induced Subgraphs and Path Decompositions	2023	Robert Hickingbotham
+ PDF Chat	Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs	2015	Konrad K. Dabrowski Daniël Paulusma
+	Clique-width of Graph Classes Defined by Two Forbidden Induced Subgraphs	2014	Konrad K. Dabrowski Daniël Paulusma
+ PDF Chat	On the number of cliques in graphs with a forbidden minor	2017	Jacob Fox Fan Wei
+ PDF Chat	Diameter and Treewidth in Minor-Closed Graph Families	2000	David Eppstein
+	On the excluded minor structure theorem for graphs of large tree-width	2012	Reinhard Diestel Ken‐ichi Kawarabayashi Theodor Müller Paul Wollan
+	Tree-width dichotomy	2020	Vadim Lozin Igor Razgon
+	A framework for minimal hereditary classes of graphs of unbounded clique-width	2022	Robert Brignall Cocks Daniel
+	Minors in graphs of large <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="mml4" display="inline" overflow="scroll" altimg="si4.gif"><mml:msub><mml:mrow><mml:mi>θ</mml:mi></mml:mrow><mml:mrow><mml:mi>r</mml:mi></mml:mrow></mml:msub></mml:math>-girth	2017	Dimitris Chatzidimitriou Jean‐Florent Raymond Ignasi Sau Dimitrios M. Thilikos
+	Infinitely many minimal classes of graphs of unbounded clique-width	2017	A. Collins Jan Foniok Nicholas Korpelainen Vadim Lozin Viktor Zamaraev
+	Graph classes with and without powers of bounded clique-width	2015	Flavia Bonomo Luciano N. Grippo Martin Milanič Martín D. Safe
+	New Graph Classes of Bounded Clique-Width	2004	Andreas Brandstädt Feodor F. Dragan Hoàng-Oanh Le Raffaele Mosca
+	On the Clique-Width of Graphs in Hereditary Classes	2002	Rodica Boliac Vadim Lozin
+ PDF Chat	A Framework for Minimal Hereditary Classes of Graphs of Unbounded Clique-Width	2023	Robert Brignall Cocks Daniel
+	Tree-width dichotomy.	2020	Vadim Lozin Igor Razgon
+	Diameter and Treewidth in Minor-Closed Graph Families, Revisited	2004	Erik D. Demaine Mohammad Taghi Hajiaghayi
+	Tree-width dichotomy	2022	Vadim Lozin Igor Razgon

Cited by (0)

Action	Title	Year	Authors

Citing (0)

Action	Title	Year	Authors