53 citations · 365 across the 52 of their papers we have counts for
22 papers · 1 filter
Polychromatic colorings of complete graphs with respect to 1-,2-factors and Hamiltonian cycles
Maria Axenovich, John Goldwasser, Ryan Hansen +5
If G is a graph and H is a set of subgraphs of G, then an edge-coloring of G is called H-polychromatic if every graph from H gets all colors present in G on its edges. The H-polych…
Ore and Chvátal-type Degree Conditions for Bootstrap Percolation from Small Sets
Michael Dairyko, Michael Ferrara, Bernard Lidický +3
Bootstrap percolation is a deterministic cellular automaton in which vertices of a graph~ begin in one of two states, "dormant" or "active". Given a fixed integer , a dormant…
A note on the size of N-free families
Ryan R. Martin, Shanise Walker
The poset consists of four distinct sets such that , , and where is not necessarily a subset of . A family $\mat…
A note on a conjecture of Gyárfás
Ryan R. Martin
This note proves that, given one member, , of a particular family of radius-three trees, every radius-two, triangle-free graph, , with large enough chromatic number contains…
On randomly generated intersecting hypergraphs
Tom Bohman, Colin Cooper, Alan Frieze +2
Let be a positive constant. We show that if and the members of are chosen sequentially at random to form an intersecting hypergraph…
How many random edges make a dense graph hamiltonian?
Tom Bohman, Alan Frieze, Ryan R. Martin
This paper investigates the number of random edges required to add to an arbitrary dense graph in order to make the resulting graph hamiltonian with high probability. Adding …
A note on -intersecting families
Tom Bohman, Ryan R. Martin
Consider a graph and a -uniform hypergraph on common vertex set . We say that is -intersecting if for every pair of edges in $X,Y \in \ma…
The emergence of a giant component in random subgraphs of pseudo-random graphs
Alan Frieze, Michael Krivelevich, Ryan R. Martin
Let be a -regular graph on vertices. Suppose that the adjacency matrix of is such that the eigenvalue which is second largest in absolute value satisfies $λ=…
On the strong chromatic number of graphs
Maria Axenovich, Ryan R. Martin
The strong chromatic number, , of an -vertex graph is the smallest number such that after adding isolated vertices to and considering {…
A note on short cycles in a hypercube
Maria Axenovich, Ryan R. Martin
How many edges can a quadrilateral-free subgraph of a hypercube have? This question was raised by Paul Erdős about years ago. His conjecture that such a subgraph asymptoticall…
Sub-Ramsey numbers for arithmetic progressions
Maria Axenovich, Ryan R. Martin
Let the integers be assigned colors. Szemerédi's theorem implies that if there is a dense color class then there is an arithmetic progression of length three in that c…
Adding random edges to dense graphs
Tom Bohman, Alan Frieze, Michael Krivelevich +1
This paper investigates the addition of random edges to arbitrary dense graphs; in particular, we determine the number of random edges required to ensure various monotone propertie…
Tripartite Version of the Corrádi-Hajnal Theorem
Csaba Magyar, Ryan R. Martin
Let be a tripartite graph with vertices in each vertex class. If each vertex is adjacent to at least vertices in each of the other classes, then either contain…
Edit distance and its computation
József Balogh, Ryan R. Martin
In this paper, we provide a method for determining the asymptotic value of the maximum edit distance from a given hereditary property. This method permits the edit distance to be c…
The diameter game
József Balogh, Ryan R. Martin, András Pluhár
A large class of Positional Games are defined on the complete graph on vertices. The players, Maker and Breaker, take the edges of the graph in turns, and Maker wins iff his su…
Expected values of parameters associated with the minimum rank of a graph
Tracy Hall, Leslie Hogben, Ryan R. Martin +1
We investigate the expected value of various graph parameters associated with the minimum rank of a graph, including minimum rank/maximum nullity and related Colin de Verdière-type…
On weighted Ramsey numbers
Maria Axenovich, Ryan Martin
The weighted Ramsey number, , is the minimum such that there is an assignment of nonnegative real numbers (weights) to the edges of with the total sum of t…
Avoiding rainbow induced subgraphs in vertex-colorings
Maria Axenovich, Ryan Martin
For a fixed graph on vertices, and a graph on at least vertices, we write if in any vertex-coloring of with colors, there is an induced sub…
On the complexity of Chooser-Picker positional games
András Csernenszky, Ryan R. Martin, András Pluhár
Two new versions of the so-called Maker-Breaker Positional Games are defined by József Beck in [{\em Combinatorica} {\bf 22}(2) (2002) 169--216]. He defines two players, Picker and…
An asymptotic multipartite Kühn-Osthus theorem
Ryan R. Martin, Richard Mycroft, Jozef Skokan
In this paper we prove an asymptotic multipartite version of a well-known theorem of Kühn and Osthus by establishing, for any graph with chromatic number , the asymptotic mu…
Regular colorings and factors of regular graphs
Anton Bernshteyn, Omid Khormali, Ryan R. Martin +4
An -coloring of an -regular graph is an edge coloring such that each vertex is incident to edges of one color and edge of a different color. In this paper…
Polychromatic Colorings on the Hypercube
John Goldwasser, Bernard Lidický, Ryan R. Martin +3
Given a subgraph G of the hypercube Q_n, a coloring of the edges of Q_n such that every embedding of G contains an edge of every color is called a G-polychromatic coloring. The max…