6 citations · 7 across the 7 of their papers we have counts for
Showing 2013Show all
3 papers · 1 filter
math.CO2013
What is Ramsey-equivalent to a clique?
Jacob Fox, Andrey Grinshpun, Anita Liebenau +2
A graph G is Ramsey for H if every two-colouring of the edges of G contains a monochromatic copy of H. Two graphs H and H' are Ramsey-equivalent if every graph G is Ramsey for H if…
math.CO2013
The Erdős-Hajnal conjecture for rainbow triangles
J. Fox, A. Grinshpun, J. Pach
We prove that every 3-coloring of the edges of the complete graph on n vertices without a rainbow triangle contains a set of order Omega(n^{1/3}log^2 n) which uses at most two colo…
cs.LO2013
Alternating Traps in Muller and Parity Games
A. Grinshpun, P. Phalitnonkiat, S. Rubin +1
Muller games are played by two players moving a token along a graph; the winner is determined by the set of vertices that occur infinitely often. The central algorithmic problem is…