Dans le problème de List k-Coloring, on nous donne un graphe dont chaque sommet est équipé d'une liste, qui est un sous-ensemble de 1, …, k. Nous devons décider si G admet un coloriage propre, où chaque sommet reçoit une couleur de sa liste. La complexité du problème dans les classes définies par l'interdiction de sous-graphes induits est un sujet largement étudié en théorie des graphes algorithmiques. Récemment, Hajebi, Li et Spirkl SIAM J. Discr. Math. 38 (2024) ont initié l'étude de List 3-Coloring dans des graphes ordonnés, c'est-à-dire, des graphes avec un ordre linéaire fixe des sommets. L'interdiction de sous-graphes induits ordonnés nous permet d'examiner plus étroitement la frontière de la tractabilité. Nous poursuivons cette direction de recherche, en nous concentrant principalement sur le cas de List 4-Coloring. Nous présentons plusieurs résultats algorithmiques et de dureté, qui fournissent ensemble une dichotomie presque complète pour les classes définies par l'interdiction d'un graphique ordonné fixé : nos investigations laissent un cas minimal ouvert.
Piecyk et al. (2026) ont étudié cette question.