2-distance coloring of sparse graphs
Abstract
Une coloration à distance 2 d'un graphe est une coloration des sommets de façon à ce que deux sommets à distance au plus deux reçoivent des couleurs différentes. On prouve que chaque graphe de degré maximum D au moins 4 et de degré moyen maximum inférieur à 7/3 admet une coloration à distance 2 utilisant (D+1) couleurs. Ce résultat est optimal, et améliore des résultats existants de Dolama et Sopena, et Borodin et al.
Origin | Files produced by the author(s) |
---|
Loading...