wovepaper · research, woven together

papers

Publications (35)

math.CO2019

Circle graphs are quadratically $I ¨ $ -bounded

James Davies, Rose McCarty

We prove that the chromatic number of a circle graph with clique number $I ¨ $ is at most $7 I ¨ ^{2}$ .

math.CO2026

Biclique decompositions from Welzl orders

Jean Cardinal, Rose McCarty, Yelena Yuditsky

A biclique decomposition of a graph is a partition of its edges into complete bipartite subgraphs. We consider graphs whose vertices can be ordered such that the neighborhood of ev…

math.CO2024

Fat minors cannot be thinned (by quasi-isometries)

James Davies, Robert Hickingbotham, Freddie Illingworth +1

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 counterexam…

math.CO2024

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 $f$ w…

cs.LO2023

First-Order Model Checking on Monadically Stable Graph Classes

Jan Dreier, Ioannis Eleftheriadis, Nikolas MÃ¤hlmann +3

A graph class $C$ is called monadically stable if one cannot interpret, in first-order logic, arbitrary large linear orders in colored graphs from $C$ . We prove…

math.CO2017

The Extremal Function and Colin de VerdiÃ¨re Graph Parameter

Rose McCarty

We study the maximum number of edges in an $n$ vertex graph with Colin de VerdiÃ¨re parameter no more than $t$ . We conjecture that for every integer $t$ , if $G$ is a graph with at…