86 citations · 344 across the 93 of their papers we have counts for
9 papers · 1 filter
An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three
Alan Frieze, Simi Haber
We describe an algorithm for finding Hamilton cycles in random graphs. Our model is the random graph $G=\gc$. In this model is drawn uniformly from graphs with vertex set …
The t-tone chromatic number of random graphs
Deepak Bal, Patrick Bennett, Andrzej Dudek +1
A proper 2-tone -coloring of a graph is a labeling of the vertices with elements from such that adjacent vertices receive disjoint labels and vertices distance…
A greedy algorithm for finding a large 2-matching on a random cubic graph
Deepak Bal, Patrick Bennett, Tom Bohman +1
A 2-matching of a graph is a spanning subgraph with maximum degree two. The size of a 2-matching is the number of edges in and this is at least $n-\k(U)$ where is t…
On the length of a random minimum spanning tree
Colin Cooper, Alan Frieze, Nate Ince +2
We study the expected value of the length of the minimum spanning tree of the complete graph when each edge is given an independent uniform edge weight. We…
On the chromatic number of a random hypergraph
Martin Dyer, Alan Frieze, Catherine Greenhill
We consider the problem of -colouring a random -uniform hypergraph with vertices and edges, where , , remain constant as tends to infinity. Achlioptas…
On the non-planarity of a random subgraph
Alan Frieze, Michael Krivelevich
Let be a finite graph with minimum degree . Form a random subgraph of by taking each edge of into independently and with probability . We prove that f…
Random triangle removal
Tom Bohman, Alan Frieze, Eyal Lubetzky
Starting from a complete graph on vertices, repeatedly delete the edges of a uniformly chosen triangle. This stochastic process terminates once it arrives at a triangle-free gr…
Rainbow Connectivity of Sparse Random Graphs
Alan Frieze, Charalampos E. Tsourakakis
An edge colored graph is rainbow edge connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connectivity of a connected graph ,…
On the game chromatic number of sparse random graphs
Alan Frieze, Simi Haber, Mikhail Lavrov
Given a graph G and an integer k, two players take turns coloring the vertices of G one by one using k colors so that neighboring vertices get different colors. The first player wi…