Zobrazeno 1 - 10
of 61
pro vyhledávání: '"Hickingbotham, Robert"'
Autor:
Campbell, Rutger, Davies, James, Distel, Marc, Frederickson, Bryce, Gollin, J. Pascal, Hendrey, Kevin, Hickingbotham, Robert, Wiederrecht, Sebastian, Wood, David R., Yepremyan, Liana
Treewidth and Hadwiger number are two of the most important parameters in structural graph theory. This paper studies graph classes in which large treewidth implies the existence of a large complete graph minor. To formalise this, we say that a graph
Externí odkaz:
http://arxiv.org/abs/2410.19295
We disprove the conjecture of Georgakopoulos and Papasoglu that a length space (or graph) with no $K$-fat $H$ minor is quasi-isometric to a graph with no $H$ minor. Our counterexample is furthermore not quasi-isometric to a graph with no 2-fat $H$ mi
Externí odkaz:
http://arxiv.org/abs/2405.09383
The defective chromatic number of a graph class $\mathcal{G}$ is the minimum integer $k$ such that for some integer $d$, every graph in $\mathcal{G}$ is $k$-colourable such that each monochromatic component has maximum degree at most $d$. Similarly,
Externí odkaz:
http://arxiv.org/abs/2404.14940
Autor:
Hickingbotham, Robert
Cop-width and flip-width are new families of graph parameters introduced by Toru\'nczyk (2023) that generalise treewidth, degeneracy, generalised colouring numbers, clique-width and twin-width. In this paper, we bound the cop-width and flip-width of
Externí odkaz:
http://arxiv.org/abs/2309.05874
The clustered chromatic number of a graph class $\mathcal{G}$ is the minimum integer $c$ such that every graph $G\in\mathcal{G}$ has a $c$-colouring where each monochromatic component in $G$ has bounded size. We study the clustered chromatic number o
Externí odkaz:
http://arxiv.org/abs/2308.15721
We prove that the $k$-power of any planar graph $G$ is contained in $H\boxtimes P\boxtimes K_{f(\Delta(G),k)}$ for some graph $H$ with bounded treewidth, some path $P$, and some function $f$. This resolves an open problem of Ossona de Mendez. In fact
Externí odkaz:
http://arxiv.org/abs/2308.06995
Autor:
Dujmović, Vida, Hickingbotham, Robert, Hodor, Jędrzej, Joret, Gweanël, La, Hoang, Micek, Piotr, Morin, Pat, Rambaud, Clément, Wood, David R.
We prove that for every planar graph $X$ of treedepth $h$, there exists a positive integer $c$ such that for every $X$-minor-free graph $G$, there exists a graph $H$ of treewidth at most $f(h)$ such that $G$ is isomorphic to a subgraph of $H\boxtimes
Externí odkaz:
http://arxiv.org/abs/2307.02816
Autor:
Dujmović, Vida, Hickingbotham, Robert, Joret, Gwenaël, Micek, Piotr, Morin, Pat, Wood, David R.
Publikováno v:
Combinatorics, Probability and Computing (2024), 33, pp. 85--90
We prove that for every tree $T$ of radius $h$, there is an integer $c$ such that every $T$-minor-free graph is contained in $H\boxtimes K_c$ for some graph $H$ with pathwidth at most $2h-1$. This is a qualitative strengthening of the Excluded Tree M
Externí odkaz:
http://arxiv.org/abs/2303.14970
A circle graph is an intersection graph of a set of chords of a circle. We describe the unavoidable induced subgraphs of circle graphs with large treewidth. This includes examples that are far from the `usual suspects'. Our results imply that treewid
Externí odkaz:
http://arxiv.org/abs/2212.11436
Autor:
Distel, Marc, Dujmović, Vida, Eppstein, David, Hickingbotham, Robert, Joret, Gwenaël, Micek, Piotr, Morin, Pat, Seweryn, Michał T., Wood, David R.
Alon, Seymour and Thomas [1990] proved that every $n$-vertex graph excluding $K_t$ as a minor has treewidth less than $t^{3/2}\sqrt{n}$. Illingworth, Scott and Wood [2022] recently refined this result by showing that every such graph is a subgraph of
Externí odkaz:
http://arxiv.org/abs/2212.08739