OPTIMAL ON-LINE COLORING OF CIRCULAR ARC GRAPHS

摘要

We show that a certain optimal on-line coloring algorithm for interval graphs given independently by Kierstead and Slusarek can be applied to a wider class of circular arc graphs. We prove that the competitive ratio of the algorithm is equal to 3 which improves a previous result by Marathe, Hunt and Ravi.%Nous montrons qu 'un certain algorithme de coloriage optimal on-line pour les graphes d'intervalles donné indépendamment par Kierstead et Slusarek, peut être appliqué à une classe plus large de graphes circulaires d'arcs. Nous montrons que l'efficacité de l'algorithme (rapport entre le nombre de couleurs utilisées dans l'algorithme et dans l'algorithme optimal) est 3, ce qui améliore un résultat précédent de Marathe, Hunt et Ravi.