17 citations · 57 across the 36 of their papers we have counts for
6 papers · 1 filter
On the clique number of random Cayley graphs and related topics
David Conlon, Jacob Fox, Huy Tuan Pham +1
We prove that a random Cayley graph on a group of order has clique number with high probability. This bound is best possible up to the constant factor f…
Treewidth, Hadwiger Number, and Induced Minors
Rutger Campbell, James Davies, Marc Distel +7
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 o…
Regular bipartite decompositions of pseudorandom graphs
Asaf Ferber, Bryce Frederickson, Dingjia Mao +2
In 1972, Kotzig proved that for every even , the complete graph can be decomposed into edge-disjoint regular bipartite spanning subgraphs, which is b…
Counterexample to Babai's lonely colour conjecture
James Davies, Meike Hatzel, Liana Yepremyan
Motivated by colouring minimal Cayley graphs, in 1978, Babai conjectured that no-lonely-colour graphs have bounded chromatic number. We disprove this in a strong sense by construct…
Longest cycles in vertex-transitive and highly connected graphs
Carla Groenland, Sean Longbrake, Raphael Steiner +2
We present progress on three old conjectures about longest paths and cycles in graphs. The first pair of conjectures, due to Lovász from 1969 and Thomassen from 1978, respectively,…
Tree Posets: Supersaturation, Enumeration, and Randomness
Tao Jiang, Sean Longbrake, Sam Spiro +1
We develop a powerful tool for embedding any tree poset of height in the Boolean lattice which allows us to solve several open problems in the area. We show that: * If …