5 citations · 9 across the 4 of their papers we have counts for
4 papers · 1 filter
A general lower bound for collaborative tree exploration
Yann Disser, Frank Mousset, Andreas Noever +2
We consider collaborative graph exploration with a set of agents. All agents start at a common vertex of an initially unknown graph and need to collectively visit all other ver…
Local resilience for squares of almost spanning cycles in sparse random graphs
Andreas Noever, Angelika Steger
In 1962, Pósa conjectured that a graph contains a square of a Hamiltonian cycle if . Only more than thirty years later Komlós, Sárkőzy, and Szemerédi prove…
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 vertex-disjoint cycles or can be made acyclic by deleting at most vertices. Here we general…
Online Ramsey Games for more than two colors
Andreas Noever
Consider the following one-player game played on an initially empty graph with vertices. At each stage a randomly selected new edge is added and the player must immediately col…