Andreas Noever

collaborators

4 papers

math.CO2017

Smaller subgraphs of minimum degree k

Frank Mousset, Andreas Noever, Nemanja Škorić

In 1990 Erdős, Faudree, Rousseau and Schelp proved that for $k \geq 2$ , every graph with $n \geq k + 1$ vertices and $(k - 1) (n - k + 2) + (2 k - 2) + 1$ edges contains a subgraph of minimu…

math.CO2016

Local resilience for squares of almost spanning cycles in sparse random graphs

Andreas Noever, Angelika Steger

In 1962, Pósa conjectured that a graph $G = (V, E)$ contains a square of a Hamiltonian cycle if $δ (G) \geq 2 n /3$ . Only more than thirty years later Komlós, Sárkőzy, and Szemerédi prove…

math.CO2016

A tight Erdős-Pósa function for long cycles

Frank Mousset, Andreas Noever, Nemanja Škorić +1

A classic result of Erdős and Pósa says that any graph contains either $k$ vertex-disjoint cycles or can be made acyclic by deleting at most $O (k lo g k)$ vertices. Here we general…

math.CO2016

Online Ramsey Games for more than two colors

Andreas Noever

Consider the following one-player game played on an initially empty graph with $n$ vertices. At each stage a randomly selected new edge is added and the player must immediately col…