Centered colorings in minor-closed graph classes
Résumé
A vertex coloring φ of a graph G is p-centered if for every connected subgraph H of G, either φ uses more than p colors on H, or there is a color that appears exactly once on H. We prove that for every fixed positive integer t, every Kt-minor-free graph admits a p-centered coloring using O(pt−1) colors.
Origine | Fichiers produits par l'(les) auteur(s) |
---|