António Girão

Two Relaxations of the Dominating Hadwiger's Conjecture

António Girão, Sergey Norin, Youri Tamitegama +1

Illingworth and Wood recently proposed the Dominating Hadwiger's Conjecture, a strengthening of Hadwiger's Conjecture which asserts that every graph with no dominating $K_{t}$ -model…

On $2$ -factors of Hamiltonian graphs

Alberto Espuny Díaz, António Girão, Bertille Granet +1

Let $k \geq 2$ . We show that, for a sufficiently small $ε > 0$ , any sufficiently large $n$ -vertex Hamiltonian graph of minimum degree at least $n^{1 - ε}$ contains a…

The Dominating 4-Colour Theorem

António Girão, Freddie Illingworth, Bojan Mohar +6

A "dominating $K_{t}$ -model" in a graph $G$ is a sequence $(T_{1}, \dots, T_{t})$ of pairwise vertex-disjoint connected subgraphs of $G$ , such that whenever $1 \leq i < j \leq t$ every vertex…

Induced subdivisions of $K_{d + 1}$ in graphs of high girth

António Girão, Zach Hunter

In this paper, we show that for all $k \geq 1 0^{8}$ , every graph with minimum degree $k$ and girth at least $1 0^{8}$ contains an induced subdivision of a $K_{k + 1}$ . This answers a probl…

math.CO2025

Cycle-factors of regular graphs via entropy

Micha Christoph, Nemanja Draganić, António Girão +3

It is a classical result that a random permutation of $n$ elements has, on average, about $lo g n$ cycles. We generalise this fact to all directed $d$ -regular graphs on $n$ vertice…

math.CO2025

New bounds for linear arboricity and related problems

Micha Christoph, Nemanja Draganić, António Girão +3

A linear forest is a collection of vertex-disjoint paths. The Linear Arboricity Conjecture states that every graph of maximum degree $Δ$ can be decomposed into at most $\lceil(Δ+1)…

Monochromatic odd cycles in edge-coloured complete graphs

António Girão, Zach Hunter

It is easy to see that every $q$ -edge-colouring of the complete graph on $2^{q} + 1$ 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 $r \geq 2$ , there exists a constant $C_{r} > 0$ with the following property: for any $0 < ε \leq 1/2$ and any graph $G$ 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 $n$ -vertex graph $G$ contains at least $γ n^{h}$ copies of a fixed $h$ -vertex graph $H$ , then $G$ contains a blowup of $H$ o…

Small families of partially shattering permutations

António Girão, Lukas Michel, Youri Tamitegama

We say that a family of permutations $t$ -shatters a set if it induces at least $t$ distinct permutations on that set. What is the minimum number $f_{k} (n, t)$ 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 $G$ and $H$ , the ordered Ramsey number $R_{<} (G, H)$ is the smallest $N$ such that whenever the edges of a vertex-ordered complete graph $K_{N}$ 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,…

Abundance: Asymmetric Graph Removal Lemmas and Integer Solutions to Linear Equations

António Girão, Eoin Hurley, Freddie Illingworth +1

We prove that a large family of pairs of graphs satisfy a polynomial dependence in asymmetric graph removal lemmas. In particular, we give an unexpected answer to a question of Gis…

math.CO2023★ 2 cited

Induced subdivisions in $K_{s, s}$ -free graphs with polynomial average degree

António Girão, Zach Hunter

In this paper we prove that for every $s \geq 2$ and every graph $H$ the following holds. Let $G$ be a graph with average degree $Ω_{H} (s^{C ∣ H ∣^{2}})$ , for some absolute constant $C > 0$ ,…

math.CO2023★ 2 cited

Induced $C_{4}$ -free subgraphs with large average degree

Xiying Du, António Girão, Zach Hunter +2

We prove that there exists a constant $C$ so that, for all $s, k \in N$ , if $G$ has average degree at least $k^{C s^{3}}$ and does not contain $K_{s, s}$ as a subgraph then it…

Flashes and rainbows in tournaments

António Girão, Freddie Illingworth, Lukas Michel +2

Colour the edges of the complete graph with vertex set ${1, 2, \dots, n}$ with an arbitrary number of colours. What is the smallest integer $f (l, k)$ such that if $n > f (l, k)$ th…

Chromatic number is not tournament-local

António Girão, Kevin Hendrey, Freddie Illingworth +4

Scott and Seymour conjectured the existence of a function $f : N \to N$ such that, for every graph $G$ and tournament $T$ on the same vertex set, $χ(G) \geqs…

Immersions of directed graphs in tournaments

António Girão, Robert Hancock

Recently, Draganić, Munhá Correia, Sudakov and Yuster showed that every tournament on $(2 + o (1)) k^{2}$ vertices contains a $1$ -subdivision of a transitive tournament on $k$ vertices,…

A note on interval colourings of graphs

Maria Axenovich, António Girão, Lawrence Hollom +5

A graph is said to be interval colourable if it admits a proper edge-colouring using palette $N$ in which the set of colours incident to each vertex is an interval. The in…