1 citations · 1 across the 24 of their papers we have counts for
7 papers · 1 filter
Reconstruction of the Path Graph
Chaya Keller, Yael Stein
Let be a set of points in convex position in the plane. The path graph of is an abstract graph whose vertices are non-crossing spanning paths of , such…
Blockers for Triangulations of a Convex Polygon and a Geometric Maker-Breaker Game
Chaya Keller, Yael Stein
Let be a complete convex geometric graph whose vertex set forms a convex polygon , and let be a family of subgraphs of . A blocker for is a set of edges, of s…
From a -Theorem to a Tight -Theorem
Chaya Keller, Shakhar Smorodinsky
A family of sets is said to satisfy the -property if among any sets of some intersect. The celebrated -theorem of Alon and Kleitman asserts that any f…
Conflict-Free Coloring of String Graphs
Chaya Keller, Alexandre Rok, Shakhar Smorodinsky
Conflict-free coloring (in short, CF-coloring) of a graph is a coloring of such that the neighborhood of each vertex contains a vertex whose color differs from the…
Conflict-Free Coloring of Intersection Graphs of Geometric Objects
Chaya Keller, Shakhar Smorodinsky
In FOCS'2002, Even et al. introduced and studied the notion of conflict-free colorings of geometrically defined hypergraphs. They motivated it by frequency assignment problems in c…
On Piercing Numbers of Families Satisfying the Property
Chaya Keller, Shakhar Smorodinsky
The Hadwiger-Debrunner number is the minimal size of a piercing set that can always be guaranteed for a family of compact convex sets in that satisfies t…
On the union complexity of families of axis-parallel rectangles with a low packing number
Chaya Keller, Shakhar Smorodinsky
Let R be a family of n axis-parallel rectangles with packing number p-1, meaning that among any p of the rectangles, there are two with a non-empty intersection. We show that the u…