Roi Krakovski

activity

20102016

most citedConflict-Free Coloring Made Stronger

11 citations · 16 across the 7 of their papers we have counts for

collaborators

Showing 2010Show all

3 papers · 1 filter

math.CO2010

Extremal results regarding $K_{6}$ -minors in graphs of girth at least 5

Elad Aigner-Horev, Roi Krakovski

We prove that every 6-connected graph of girth $\geq 6$ has a $K_{6}$ -minor and thus settle the Jorgensen conjecture for graphs of girth $\geq 6$ . Relaxing the assumption on the gir…

math.CO2010

The Kelmans-Seymour conjecture for apex graphs

Elad Aigner-Horev, Roi Krakovski

We provide a short proof that a 5-connected nonplanar apex graph contains a subdivided $K_{_{5}}$ or a $K_{_{4}}^{-}$ (= $K_{_{4}}$ with a single edge removed) as a subgraph. Together with…

math.CO2010★ 11 cited

Conflict-Free Coloring Made Stronger

Elad Horev, Roi Krakovski, Shakhar Smorodinsky

In FOCS 2002, Even et al. showed that any set of $n$ discs in the plane can be Conflict-Free colored with a total of at most $O (lo g n)$ colors. That is, it can be colored with $O(…

Extremal results regarding K6​-minors in graphs of girth at least 5

The Kelmans-Seymour conjecture for apex graphs

Conflict-Free Coloring Made Stronger

Extremal results regarding $K_{6}$ -minors in graphs of girth at least 5