9 citations · 33 across the 9 of their papers we have counts for
12 papers · 1 filter
Sharp Thresholds for Factors in Random Graphs
Fabian Burghart, Annika Heckel, Marc Kaufmann +2
Let be a graph on vertices and let be a graph on vertices. Then an -factor in is a subgraph of composed of vertex-disjoint copies of , if di…
The difference between the chromatic and the cochromatic number of a random graph
Annika Heckel
The cochromatic number of a graph is the minimum number of colours needed for a vertex colouring where every colour class is either an independent set or a clique. Let $…
On a question of Erdős and Gimbel on the cochromatic number
Annika Heckel
In this note, we show that the difference between the chromatic and the cochromatic number of the random graph is not whp bounded by , addressing a questi…
Colouring random graphs: Tame colourings
Annika Heckel, Konstantinos Panagiotou
Given a graph G, a colouring is an assignment of colours to the vertices of G so that no two adjacent vertices are coloured the same. If all colour classes have size at most t, the…
The hitting time of clique factors
Annika Heckel, Marc Kaufmann, Noela Müller +1
In a recent paper, Kahn gave the strongest possible, affirmative, answer to Shamir's problem, which had been open since the late 1970s: Let and let be divisible by $…
How does the chromatic number of a random graph vary?
Annika Heckel, Oliver Riordan
How does the chromatic number of a graph chosen uniformly at random from all graphs on vertices behave? This quantity is a random variable, so one can ask (i) for upper and low…
Non-concentration of the chromatic number of a random graph
Annika Heckel
We show that the chromatic number of is not concentrated on fewer than consecutive values. This addresses a longstanding question rai…
Random triangles in random graphs
Annika Heckel
In a recent paper, Oliver Riordan shows that for and up to and slightly larger than the threshold for a -factor, the hypergraph formed by the copies of in…
Sharp concentration of the equitable chromatic number of dense random graphs
Annika Heckel
An equitable colouring of a graph is a colouring of the vertices of so that no two adjacent vertices are coloured the same and, additionally, the colour class sizes differ…
The chromatic number of dense random graphs
Annika Heckel
The chromatic number of a graph is defined as the minimum number of colours required for a vertex colouring where no two adjacent vertices are coloured the same. The chr…
On the threshold for rainbow connection number r in random graphs
Annika Heckel, Oliver Riordan
We call an edge colouring of a graph G a rainbow colouring if every pair of vertices is joined by a rainbow path, i.e., a path where no two edges have the same colour. The minimum…
The hitting time of rainbow connection number two
Annika Heckel, Oliver Riordan
In a graph with a given edge colouring, a rainbow path is a path all of whose edges have distinct colours. The minimum number of colours required to colour the edges of so…