%0 Journal Article %T Tight online conflict-free coloring of intervals %J Scientia Iranica %I Sharif University of Technology %Z 1026-3098 %A Abam, M.A. %D 2021 %\ 06/01/2021 %V 28 %N Special issue on collective behavior of nonlinear dynamical networks %P 1493-1496 %! Tight online conflict-free coloring of intervals %K ‎Frequency Assignment‎ %K ‎Conflict-Free Coloring‎ %K ‎Intervals‎ %K ‎On-line Algorithms‎ %K ‎Computational Geometry %R 10.24200/sci.2020.54600.3826 %X ‎We ‎revisit the problem of online conflict-free coloring of intervals on a line‎, ‎where each newly inserted interval must be assigned a color upon insertion such that the coloring remains conflict-free‎, ‎i.e‎. ‎for each point $p$ in the union of the current intervals‎, ‎there must be an interval $I$ with a unique color among all intervals covering $p$‎. ‎To best of our knowledge, the ‎best-‎known ‎algorithm ‎uses‎ $O(\log^3 n )$ ‎colors, where $n$ is the number of current intervals‎. ‎We‎ present a simple greedy algorithm that uses only $O(\log n)$ colors. Therefore, we settle down the open problem raised in \cite{ars1‎4‎}. %U https://scientiairanica.sharif.edu/article_22068_c78602be375ed7f3f9d321aa6f47f3f2.pdf