Simple Sublinear Algorithms for Vertex Coloring via Asymmetric Palette Sparsification
Cet article présente un théorème de sparsification de palette asymétrique qui, en permettant des tailles de listes variables et en autorisant l'utilisation d'un algorithme de coloration glouton simple, surmonte les complexités techniques et algorithmiques des preuves antérieures tout en maintenant des performances quasi optimales pour le coloriage des sommets dans divers modèles sous-linéaires.