Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs

Julia Böttcher, Klaas P. Pruessmann, Anusch Taraz, Andreas Würfl

Type: Article

Publication Date: 2009-10-25

Citations: 62

DOI: https://doi.org/10.1016/j.ejc.2009.10.010

View Publication

Download PDF

Locations

European Journal of Combinatorics - View
arXiv (Cornell University) - PDF

Similar Works

Action	Title	Year	Authors
+	Bandwidth, expansion, treewidth, separators, and universality for bounded degree graphs	2009	Julia Böttcher Klaas P. Pruessmann Anusch Taraz Andreas Würfl
+ PDF Chat	The bandwidth theorem for locally dense graphs	2020	Katherine Staden Andrew Treglown
+	Graphs of bounded tree width	2017	Martin Grohe
+	Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)	2022	Édouard Bonnet O‐joung Kwon David R. Wood
+	On the relation of separability, bandwidth and embedding	2018	Béla Csaba Bálint Márk Vásárhelyi
+	On the relation of separability, bandwidth and embedding	2018	Béla Csaba Bálint Márk Vásárhelyi
+	Bandwidth, treewidth, separators, expansion, and universality	2008	Julia Böttcher Klaas P. Pruessmann Anusch Taraz Andreas Würfl
+	The Bandwidth Theorem in Sparse Graphs	2016	Peter Allen Julia Böttcher Julia Ehrenmüller Anusch Taraz
+	The Bandwidth Theorem in Sparse Graphs	2016	Peter J. Allen Julia Böttcher Julia Ehrenmüller Anusch Taraz
+	Classes of graphs with bounded tree-width	1986	Hans L. Bodlaender
+	Algorithms for Classes of Graphs with Bounded Expansion	2009	Zdeněk Dvořák Daniel Kráľ
+ PDF Chat	Planar graphs in blowups of fans	2024	Vida Dujmović Gwenaël Joret Piotr Micek Pat Morin David R. Wood
+ PDF Chat	On the Relation of Separability, Bandwidth and Embedding	2019	Béla Csaba Bálint Márk Vásárhelyi
+ PDF Chat	Universal Graphs for Bounded-Degree Trees and Planar Graphs	1989	Sandeep Bhatt Fan Chung Frank Thomson Leighton Arnold L. Rosenberg
+	Treewidth versus clique number in graph classes with a forbidden structure	2020	Clément Dallard Martin Milanič Kenny Štorgel
+	Graphs with small bandwidth and cutwidth	1989	Fan Chung Paul Seymour
+	A bandwidth theorem for graph transversals	2023	Debsoumya Chakraborti Seonghyuk Im Jaehoon Kim Hong Liu
+	Graphs with maximum size and lower bounded girth	2011	E. Abajo A. Diánez
+	Hitting (topological) minors on bounded treewidth graphs	2017	Julien Baste Ignasi Sau Dimitrios M. Thilikos
+ PDF Chat	The Bandwidth Theorem in sparse graphs	2020	Peter Allen Julia Böttcher Julia Ehrenmüller Anusch Taraz

Works That Cite This (56)

Action	Title	Year	Authors
+	An approximate blow-up lemma for sparse pseudorandom graphs	2013	Peter Allen Julia Böttcher Hiệp Hàn Yoshiharu Kohayakawa Yury Person
+	Ramsey numbers for bipartite graphs with small bandwidth	2015	Guilherme Oliveira Mota Gábor N. Sárközy Mathias Schacht Anusch Taraz
+ PDF Chat	Ramsey-goodness—and otherwise	2013	Peter Allen Graham Brightwell Jozef Skokan
+	Forcing spanning subgraphs via Ore type conditions	2009	Julia Böttcher Sybille Müller
+	Universality of random graphs and rainbow embedding	2013	Asaf Ferber Rajko Nenadov Ueli Peter
+	A tight Erd\H{o}s-P\'osa function for long cycles	2016	Frank Mousset Andreas Noever Nemanja Škorić Felix Weissenberger
+	On the bandwidth of the Kneser graph	2017	Tao Jiang Zevi Miller Derrek Yager
+	Bandwidth theorem for random graphs	2011	Hao Huang Choongbum Lee Benny Sudakov
+ PDF Chat	A tight Erdős–Pósa function for long cycles	2017	Frank Mousset Andreas Noever Nemanja Škorić Felix Weissenberger
+ PDF Chat	Almost spanning subgraphs of random graphs after adversarial edge removal	2009	Julia Böttcher Yoshiharu Kohayakawa Anusch Taraz

Works Cited by This (12)

Action	Title	Year	Authors
+	On the square of a Hamiltonian cycle in dense graphs	1996	J�nos Koml�s G�bor N. S�rk�zy Endre Szemer�di
+ PDF Chat	Embedding large subgraphs into dense graphs	2009	Daniela Kühn Deryk Osthus
+	Proof of the bandwidth conjecture of Bollobás and Komlós	2008	Julia Böttcher Mathias Schacht Anusch Taraz
+ PDF Chat	Graph drawings with few slopes	2006	Vida Dujmović Matthew Suderman David R. Wood
+ PDF Chat	Universal Graphs for Bounded-Degree Trees and Planar Graphs	1989	Sandeep Bhatt Fan Chung Frank Thomson Leighton Arnold L. Rosenberg
+	The Square of Paths and Cycles	1995	Genghua Fan H. A. Kierstead
+	Graph Minors. XX. Wagner's conjecture	2004	Neil Robertson Paul Seymour
+	Large planar subgraphs in dense graphs	2005	Daniela Kühn Deryk Osthus Anusch Taraz
+	Proof of a tiling conjecture of Komlós	2003	Ali Shokoufandeh Yi Zhao
+ PDF Chat	A separator theorem for nonplanar graphs	1990	Noga Alon Paul Seymour Robin Thomas