67 citations · 244 across the 17 of their papers we have counts for
23 papers
Property B for random non-uniform hypergraphs
Grzegorz Ryn, Jakub Kozik
We show that, in random hypergraphs with several permitted edge sizes, non-uniformity affects existential and algorithmic bounds for 2-colorability (Property B) in fundamentally di…
Local Computation Algorithms for Hypergraph Coloring -- following Beck's approach (full version)
Andrzej Dorobisz, Jakub Kozik
We investigate local computation algorithms (LCA) for two-coloring of -uniform hypergraphs. We focus on hypergraph instances that satisfy strengthened assumption of the Lovász L…
Schnyder woods and Alon-Tarsi number of planar graphs
Jakub Kozik, Bartosz Podkanowicz
Thomassen in 1994 published a famous proof of the fact that the choosability of a planar graph is at most 5. Zhu in 2019 generalized this result by showing that the same bound hold…
Local Computation Algorithms for Coloring of Uniform Hypergraphs
Andrzej Dorobisz, Jakub Kozik
We present a progress on local computation algorithms for two coloring of -uniform hypergraphs. We focus on instances that satisfy strengthened assumption of Local Lemma of the…
Random hypergraphs and property B
Lech Duraj, Jakub Kozik, Dmitry Shabanov
In 1964 Erdős proved that $(1+\oh{1})) \frac{\eul \ln(2)}{4} k^2 2^{k}$ edges are sufficient to build a -graph which is not two colorable. To this day, it is not known whether t…
Improving Gebauer's construction of 3-chromatic hypergraphs with few edges
Jakub Kozik
In 1964 Erdős proved, by randomized construction, that the minimum number of edges in a -graph that is not two colorable is . To this day, it is not known whether…