7 citations · 26 across the 38 of their papers we have counts for
9 papers · 1 filter
Monochromatic odd cycles in edge-coloured complete graphs
António Girão, Zach Hunter
It is easy to see that every -edge-colouring of the complete graph on vertices must contain a monochromatic odd cycle. A natural question raised by Erdős and Graham in $…
Sparse Partitions of Graphs with Bounded Clique Number
António Girão, Toby Insley
We prove that for each integer , there exists a constant with the following property: for any and any graph with clique number at most…
A bounded diameter strengthening of Kőnig's Theorem
Louis DeBiasio, António Girão, Penny Haxell +1
K\H onig's theorem says that the vertex cover number of every bipartite graph is at most its matching number (in fact they are equal since, trivially, the matching number is at mos…
Blowups of triangle-free graphs
António Girão, Zach Hunter, Yuval Wigderson
A highly influential result of Nikiforov states that if an -vertex graph contains at least copies of a fixed -vertex graph , then contains a blowup of o…
Small families of partially shattering permutations
António Girão, Lukas Michel, Youri Tamitegama
We say that a family of permutations -shatters a set if it induces at least distinct permutations on that set. What is the minimum number of permutations of $\{1,…
Embedding induced trees in sparse expanding graphs
António Girão, Eoin Hurley
Inspired by the network routing literature \cite{aggarwal1996efficient}, we develop what we call a ``Pre-Emptive Greedy Algorithm" to embed bounded degree induced trees in sparse e…
Seymour's second neighbourhood conjecture: random graphs and reductions
Alberto Espuny Díaz, António Girão, Bertille Granet +1
A longstanding conjecture of Seymour states that in every oriented graph there is a vertex whose second outneighbourhood is at least as large as its outneighbourhood. In this short…
Ordered Ramsey numbers of powers of paths
António Girão, Barnabás Janzer, Oliver Janzer
Given two vertex-ordered graphs and , the ordered Ramsey number is the smallest such that whenever the edges of a vertex-ordered complete graph are red/…
Non-Homotopic Drawings of Multigraphs
António Girão, Freddie Illingworth, Alex Scott +1
A multigraph drawn in the plane is non-homotopic if no two edges connecting the same pair of vertices can be continuously deformed into each other without passing through a vertex,…