Patrick Bennett

activity

20122026

most citedA natural barrier in random greedy hypergraph matching

19 citations · 46 across the 26 of their papers we have counts for

collaborators

Showing 2012Show all

3 papers · 1 filter

math.CO2012

The t-tone chromatic number of random graphs

Deepak Bal, Patrick Bennett, Andrzej Dudek +1

A proper 2-tone $k$ -coloring of a graph is a labeling of the vertices with elements from $(2 [ k ])$ such that adjacent vertices receive disjoint labels and vertices distance…

math.CO2012★ 19 cited

A natural barrier in random greedy hypergraph matching

Patrick Bennett, Tom Bohman

Let $r \geq 2$ be a fixed constant and let $H$ be an $r$ -uniform, $D$ -regular hypergraph on $N$ vertices. Assume further that $D \to \infty$ as $N \to \infty$ and that…

math.CO2012

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 $G$ is a spanning subgraph with maximum degree two. The size of a 2-matching $U$ is the number of edges in $U$ and this is at least $n-\k(U)$ where $n$ is t…