Le problème de la détermination du plus grand sous-graphe \(k\)-colorable (\(k\)-MCSP) consiste à colorer autant de sommets que possible avec au plus \(k\) couleurs, de telle sorte que les sommets adjacents n'aient pas la même couleur. Nous considérons des algorithmes en ligne (online) pour ce problème \(\mathcal{NP}\)-dur, et nous donnons des bornes sur leur ratio de compétitivité. Nous considérons ensuite une famille \(\cal{A}\) d'algorithmes de coloration séquentielle en ligne, et nous déterminons les plus petits graphes pour lesquels aucun algorithme de la famille \(\cal{A}\) n'est capable de générer une solution optimale au problème \(k\)-MCSP. Nous comparons ensuite les performances de plusieurs algorithmes en ligne de coloration séquentielle, en utilisant les graphes de la banque de données DIMACS. Finalement, nous considérons le cas où les sommets colorés d'une certaine étape peuvent recevoir une nouvelle couleur plus tard, pour autant qu'ils demeurent colorés.