1 citations · 1 across the 7 of their papers we have counts for
6 papers · 1 filter
Burling graphs in graphs with large chromatic number
Tara Abrishami, Marcin Briański, James Davies +4
A graph class is -bounded if the only way to force large chromatic number in graphs from the class is by forming a large clique. In the 1970s, Erdős conjectured that intersectio…
String graphs are quasi-isometric to planar graphs
James Davies
We prove that for every countable string graph , there is a planar graph with such that \[ \frac{1}{23660800}d_S(u,v) \le d_G(u,v) \le 162 d_S(u,v) \] for all $u…
Counterexample to the conjectured coarse grid theorem
Sandra Albrechtsen, James Davies
We show that for every there exists a graph that does not contain the -grid as a -fat minor and is not -quasi-isometric to a g…
Colouring t-perfect graphs
Maria Chudnovsky, Linda Cook, James Davies +2
Perfect graphs can be described as the graphs whose stable set polytopes are defined by their non-negativity and clique inequalities (including edge inequalities). In 1975, Chvátal…
On high genus extensions of Negami's conjecture
Marcin Briański, James Davies, Jane Tan
Negami's famous planar cover conjecture is equivalent to the statement that a connected graph can be embedded in the projective plane if and only if it has a projective planar cove…
Polynomial Gyárfás-Sumner conjecture for graphs of bounded boxicity
James Davies, Yelena Yuditsky
We prove that for every positive integer and forest , the class of intersection graphs of axis-aligned boxes in with no induced subgraph is (polynomially)…