29 citations · 74 across the 56 of their papers we have counts for
5 papers · 1 filter
Set systems related to a house allocation problem
Dániel Gerbner, Balázs Keszegh, Abhishek Methuku +4
We are given a set of buyers, a set of houses, and for each buyer a preference list, i.e., an ordering of the houses. A house allocation is an injective mapping from $A…
Two-coloring triples such that in each color class every element is missed at least once
Balázs Keszegh
We give a characterization of finite sets of triples of elements (e.g., positive integers) that can be colored with two colors such that for every element in each color class t…
A note about online nonrepetitive coloring -trees
Balázs Keszegh, Xuding Zhu
We prove that it is always possible to color online nonrepetitively any (partial) -tree (that is, graphs with tree-width at most ) with colors. This implies that it is…
Adaptive Majority Problems for Restricted Query Graphs and for Weighted Sets
Gábor Damásdi, Dániel Gerbner, Gyula O. H. Katona +8
Suppose that the vertices of a graph are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it…
Coloring hypergraphs defined by stabbed pseudo-disks and ABAB-free hypergraphs
Eyal Ackerman, Balázs Keszegh, Dömötör Pálvölgyi
What is the minimum number of colors that always suffice to color every planar set of points such that any disk that contains enough points contains two points of different colors?…