Centered colorings in minor-closed graph classes - Graphes, Algorithmes et Combinatoire
Pré-Publication, Document De Travail Année : 2024

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(pt1) colors.
Fichier principal
Vignette du fichier
2411.02122v1.pdf (1.04 Mo) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04819300 , version 1 (04-12-2024)

Licence

Identifiants

Citer

Jȩdrzej Hodor, Hoang La, Piotr Micek, Clément Rambaud. Centered colorings in minor-closed graph classes. 2024. ⟨hal-04819300⟩
0 Consultations
0 Téléchargements

Altmetric

Partager

More