Coloration à distance 2 des graphes épars
Xuan Hoang La · theses.fr (ABES) · 2022
Dans cette thèse, on étudie le nombre chromatique à distance 2 des graphes épars, à savoir, les graphes planaires et les graphes avec degré moyen maximum borné. Les bornes supérieures sont obtenues en repoussand les limites de la méthode du déchargement. En particulier, on la combine avec la méthode du potentiel. De plus, on développe un cadre informatique pour la procédure de déchargement. On fournit aussi des constructions pour les bornes inférieures sur le nombre chromatique à distance 2. Finalement, on étudie les variantes, à savoir, la coloration r-nuancée, la coloration injective, et la coloration du carré exact.