23 citations · 54 across the 45 of their papers we have counts for
4 papers · 1 filter
Color-Critical Graphs Have Logarithmic Circumference
Asaf Shapira, Robin Thomas
A graph G is k-critical if every proper subgraph of G is (k-1)-colorable, but the graph G itself is not. We prove that every k-critical graph on n vertices has a cycle of length at…
The Effect of Induced Subgraphs on Quasi-Randomness
Asaf Shapira, Raphael Yuster
One of the main questions that arise when studying random and quasi-random structures is which properties P are such that any object that satisfies P "behaves" like a truly random…
On the Density of a Graph and its Blowup
Asaf Shapira, Raphael Yuster
The theorem of Chung, Graham, and Wilson on quasi-random graphs asserts that of all graphs with edge density p, the random graph G(n,p) contains the smallest density of copies of K…
Multigraphs (only) satisfy a weak triangle removal lemma
Asaf Shapira, Raphael Yuster
The triangle removal lemma states that a simple graph with o(n^3) triangles can be made triangle-free by removing o(n^2) edges. It is natural to ask if this widely used result can…