J. Kozik

activity

20112026

most citedTriangle-free intersection graphs of line segments with large chromatic number

67 citations · 244 across the 17 of their papers we have counts for

collaborators

Showing 2013Show all

2 papers · 1 filter

math.CO2013

A note on random greedy coloring of uniform hypergraphs

Danila D. Cherkashin, Jakub Kozik

The smallest number of edges forming an n-uniform hypergraph which is not r-colorable is denoted by m(n,r). Erdős and Lovász conjectured that m(n,2)=θ(n 2^n)$. The best known lower…

math.CO2013

Multipass greedy coloring of simple uniform hypergraphs

Jakub Kozik

Let $m^{*} (n)$ be the minimum number of edges in an $n$ -uniform simple hypergraph that is not two colorable. We prove that $m^{*} (n) = Ω (4^{n} / ln^{2} (n))$ . Our result generalizes to $r$ -col…