A. Scott

activity

20062022

most citedMonochromatic cycles and the monochromatic circumference in 2-coloured graphs

5 citations · 15 across the 13 of their papers we have counts for

collaborators

Showing 2019Show all

7 papers · 1 filter

math.CO2019

Monochromatic Components in Edge-Coloured Graphs with Large Minimum Degree

Hannah Guggiari, Alex Scott

For every $n \in N$ and $k \geq 2$ , it is known that every $k$ -edge-colouring of the complete graph on $n$ vertices contains a monochromatic connected component of order at le…

math.CO2019

Shotgun reconstruction in the hypercube

Michał Przykucki, Alexander Roberts, Alex Scott

Mossel and Ross raised the question of when a random colouring of a graph can be reconstructed from local information, namely the colourings (with multiplicity) of balls of given r…

math.CO2019

Detecting a long odd hole

Maria Chudnovsky, Alex Scott, Paul Seymour

For each integer $t \geq 5$ , we give a polynomial-time algorithm to test whether a graph contains an induced cycle with length at least $t$ and odd.

math.CO2019

Detecting an odd hole

Maria Chudnovsky, Alex Scott, Paul Seymour +1

A hole in a graph G is an induced cycle of length at least four; an antihole is a hole in the complement of G. In 2005, Chudnovsky, Cornuejols, Liu, Seymour and Vuskovic showed tha…

math.CO2019

Concatenating bipartite graphs

Maria Chudnovsky, Patrick Hompe, Alex Scott +2

Let $x, y \in (0, 1]$ and let $A, B, C$ be disjoint nonempty subsets of a graph $G$ , where every vertex in $A$ has at least $x ∣ B ∣$ neighbours in $B$ , and every vertex in $B$ has at least…

math.CO2019

Maximising the Number of Cycles in Graphs with Forbidden Subgraphs

Natasha Morrison, Alexander Roberts, Alex Scott

Fix $k \geq 2$ and let $H$ be a graph with $χ (H) = k + 1$ containing a critical edge. We show that for sufficiently large $n$ , the unique $n$ -vertex $H$ -free graph containing the maxi…