Sharif University of TechnologyScientia Iranica1026-309821620141201Online conflict-free coloring of intervalsOnline conflict-free coloring of intervals213821413607ENM.A.AbamDepartment of Computer Engineering, Sharif University of Technology, Tehran, IranM.J.Rezaei SerajiDepartment of Computer Engineering, Sharif University of Technology, Tehran, IranM.ShadravanDepartment of Computer Engineering, Sharif University of Technology, Tehran, IranJournal Article20141231In this paper, we study 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. We first present a simple algorithm which uses O(pn) colors where n is the number of current intervals. Next, we propose an CF-coloring of intervals which uses O(log3 n) colorshttp://scientiairanica.sharif.edu/article_3607_437db4a9645b9db91954fd85067f04d2.pdf