Optimal on-line coloring of circular arc graphs
Maciej Ślusarek · RAIRO - Theoretical Informatics and Applications · 1995
We show that a certain optimal on-line coloring algorithmfor interval graphs given independently by Kierstead and Slusarek can be applied to a wider class of circular arc graphs.We prove that the compétitive ratio ofthe algorithm is equal to 3 which improves a previous resuit by Marathe, Hunt and Ravi.Résumé.-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.