5 papers · 1 filter
Asymptotic Bounds for Online Ramsey Numbers of Stars versus Long Paths and Cycles
Sam Beilis, Israel R. Curbelo, Elizabeth R. Koizumi
The online Ramsey game for graphs and is played on the infinite complete graph . In each round, Builder chooses an edge, and Painter colors it red or blue. Th…
On the asymptotic behavior of online Ramsey numbers for stars, paths and cycles
Sam Beilis, Israel R. Curbelo
The online Ramsey game for graphs and is played on the infinite complete graph . Each round, Builder chooses an edge, and Painter colors it red or blue. The o…
On the on-line coloring of unit interval graphs with proper interval representation
Israel R. Curbelo, Hannah R. Malko
We define the problem as a two-player game between Algorithm and Builder. The game is played in rounds. Each round, Builder presents an interval that is neither contained in nor co…
Improved lower bounds on the on-line chain partitioning of posets of bounded dimension
Csaba Biró, Israel R. Curbelo
An on-line chain partitioning algorithm receives a poset, one element at a time, and irrevocably assigns the element to one of the chains. Over 30 years ago, Szemerédi proved that…
Improved lower bound on the on-line chain partitioning of semi-orders with representation
Csaba Biró, Israel R. Curbelo
An on-line chain partitioning algorithm receives a poset, one element at a time, and irrevocably assigns the element to one of the chains in the partition. The on-line chain partit…