4 citations · 8 across the 6 of their papers we have counts for
6 papers
Optimal Hardness of Online Algorithms for Large Independent Sets
David Gamarnik, Eren C. Kızıldağ, Lutz Warnke
We study the algorithmic problem of finding a large independent set in the Erd{ö}s-Rényi random graph . For constant and , the largest independent set has si…
The clique chromatic number of sparse random graphs
Manuel Fernandez, Lutz Warnke
The clique chromatic number of a graph is the smallest number of colors in a vertex coloring so that no maximal clique is monochromatic. In this paper, we determine the order of ma…
Two-Point Concentration of the Domination Number of Random Graphs
Tom Bohman, Lutz Warnke, Emily Zhu
We show that the domination number of the binomial random graph G_{n,p} with edge-probability p is concentrated on two values for p \ge n^{-2/3+\eps}, and not concentrated on two v…
Extreme local statistics in random graphs: maximum tree extension counts
Pedro Araújo, Simon Griffiths, Matas Šileikis +1
We consider maximum rooted tree extension counts in random graphs, i.e., we consider M_n = \max_v X_v where X_v counts the number of copies of a given tree in G_{n,p} rooted at ver…
On the concentration of the chromatic number of random graphs
Erlang Surya, Lutz Warnke
Shamir and Spencer proved in the 1980s that the chromatic number of the binomial random graph G(n,p) is concentrated in an interval of length at most ω\sqrt{n}, and in the 1990s Al…
On the concentration of the chromatic number of random graphs
Alex Scott
Let 0<p<1 be fixed. Shamir and Spencer proved in the 1980s that the chromatic number of a random graph in G(n,p) is concentrated in an interval of length about n^{1/2}. In this exp…