30 citations · 74 across the 13 of their papers we have counts for
8 papers · 1 filter
Universality for graphs with bounded density
Noga Alon, Natalie Dodson, Carmen Jackson +3
A graph is for a (finite) family of graphs if every is a subgraph of . For a given family , the goal is t…
Prime and polynomial distances in colourings of the plane
James Davies, Rose McCarty, Michał Pilipczuk
We give two extensions of the recent theorem of the first author that the odd distance graph has unbounded chromatic number. The first is that for any non-constant polynomial w…
Decomposing a signed graph into rooted circuits
Rose McCarty
We prove a precise min-max theorem for the following problem. Let be an Eulerian graph with a specified set of edges , and let be a vertex of . Then wh…
Induced -free subgraphs with large average degree
Xiying Du, António Girão, Zach Hunter +2
We prove that there exists a constant so that, for all , if has average degree at least and does not contain as a subgraph then it…
Sparse induced subgraphs in P_6-free graphs
Maria Chudnovsky, Rose McCarty, Marcin Pilipczuk +2
We prove that a number of computational problems that ask for the largest sparse induced subgraph satisfying some property definable in CMSO2 logic, most notably Feedback Vertex Se…
Geometric Graphs with Unbounded Flip-Width
David Eppstein, Rose McCarty
We consider the flip-width of geometric graphs, a notion of graph width recently introduced by Toruńczyk. We prove that many different types of geometric graphs have unbounded flip…
On tree decompositions whose trees are minors
Pablo Blanco, Linda Cook, Meike Hatzel +3
In 2019, Dvořák asked whether every connected graph has a tree decomposition so that is a subgraph of and the width of is bounded…
Flipper games for monadically stable graph classes
Jakub Gajarský, Nikolas Mählmann, Rose McCarty +6
A class of graphs is monadically stable if for any unary expansion of , one cannot interpret, in first-order logic, arbitrarily l…