21 citations · 39 across the 20 of their papers we have counts for
Showing 2022Show all
2 papers · 1 filter
math.CO2022
Mrs. Correct and Majority Colorings
Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk +3
A majority coloring of a directed graph is a vertex coloring in which each vertex has the same color as at most half of its out-neighbors. In this note we simplify some proof techn…
cs.DM2022
Recoloring Unit Interval Graphs with Logarithmic Recourse Budget
Bartłomiej Bosek, Anna Zych-Pawlewicz
In this paper we study the problem of coloring a unit interval graph which changes dynamically. In our model the unit intervals are added or removed one at the time, and have to be…