Paper Info
Title
Online and quasi-online colorings of wedges and intervals
Abstract
We consider proper online colorings of hypergraphs defined by geometric regions. We prove that there is an online coloring algorithm that colors intervals of the real line using colors such that for every point , contained in at least intervals, not all the intervals containing have the same color. We also prove the corresponding result about online coloring a family of wedges (quadrants) in the plane that are the translates of a given fixed wedge. These results contrast the results of the first and third author showing that in the quasi-online setting 12 colors are enough to color wedges (independent of and ). We also consider quasi-online coloring of intervals. In all cases we present efficient coloring algorithms.
Year
DOI
Venue
2013
10.1007/s11083-015-9374-8
Order
Keywords
DocType
Volume
Proper coloring,Intervals,Quadrants,Online
Conference
33
Issue
ISSN
Citations 
3
0167-8094
1
PageRank 
References 
Authors
0.37
16
3
Name
Order
Citations
PageRank
Balázs Keszegh115624.36
Nathan Lemons2679.49
Dömötör Pálvölgyi320229.14