Keszegh, Balázs and Lemons, Nathan and Pálvölgyi, Dömötör (2013) Online and quasi-online colorings of wedges and intervals. LECTURE NOTES IN COMPUTER SCIENCE, 7741. pp. 292-306. ISSN 0302-9743
|
Text
1207.4415v2.pdf Available under License Creative Commons Attribution. Download (266kB) | Preview |
Abstract
We consider proper online colorings of hypergraphs defined by geometric regions. We prove that there is an online coloring method that colors N intervals of the real line using Θ(logN/k) colors such that for every point p, contained in at least k intervals, not all the intervals containing p have the same color. We also prove the corresponding result about online coloring quadrants in the plane that are parallel to a given fixed quadrant. These results contrast to recent results of the first and third author showing that in the quasi-online setting 12 colors are enough to color quadrants (independent of N and k). We also consider coloring intervals in the quasi-online setting. In all cases we present efficient coloring algorithms as well.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | COLOR; coloring; Computer science; Hyper graph; On-line coloring; Real line; Coloring algorithms; |
| Subjects: | Q Science / természettudomány > Q1 Science (General) / természettudomány általában |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 23 May 2024 13:52 |
| Last Modified: | 23 May 2024 13:52 |
| URI: | https://real.mtak.hu/id/eprint/195564 |
Actions (login required)
 |
Edit Item |
