3 papers
math.CO2026
Arboricity Nearly Bounds Degeneracy
Michał Lasoń, Bartłomiej Bosek, Grzegorz Gutowski +1
Arboricity and degeneracy are two fundamental and closely related graph parameters that measure the sparsity of a graph. Every -degenerate graph is -arboric, but some -arb…
math.CO2025
Alon-Tarsi for hypergraphs
Marcin Anholcer, Bartłomiej Bosek, Grzegorz Gutowski +6
Given a hypergraph , define for every edge a linear expression with arguments corresponding to the vertices. Next, let the polynomial be the product of such…
cs.DM2024
First-Fit Coloring of Forests in Random Arrival Model
Bartłomiej Bosek, Grzegorz Gutowski, Michał Lasoń +1
We consider a graph coloring algorithm that processes vertices in order taken uniformly at random and assigns colors to them using First-Fit strategy. We show that this algorithm u…