21 citations · 39 across the 20 of their papers we have counts for
Showing 2024Show all
2 papers · 1 filter
cs.DM2024
A Note About Majority Colorings of Countable DAGs
Bartłomiej Bosek, Aleksander Katan
A majority coloring of an undirected graph is a vertex coloring in which for each vertex there are at least as many bi-chromatic edges containing that vertex as monochromatic ones.…
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…