New Bounds for Proper h‐Conflict‐Free Colorings
Random Structures & Algorithms · 2026-03 · 68 (2)
DOI: 10.1002/rsa.70054 ↗Kurz gefasst
Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 03.03.2026. Verfasst von Quentin Chuet und 3 weiteren Autor:innen. Die Arbeit nennt 15 Literaturangaben. Gefördert von: Natural Science Foundation of Shandong Province.
Abstract (Originalsprache)
A proper ‐coloring of a graph is called ‐conflict‐free if every vertex has at least colors appearing exactly once in its neighborhood. Let denote the minimum such that such a coloring exists. We show that for every fixed , every graph of maximum degree satisfies . This expands on the work of Cho et al., and improves a recent result of Liu and Reed in the case . We conjecture that for every and every graph of maximum degree sufficiently large, the bound should hold, which would be tight. When the minimum degree of is sufficiently large, namely , we show that this upper bound can be further reduced to . This improves a recent bound from Kamyczura and Przybyło when .
Förderung
- Natural Science Foundation of Shandong Province
Zitieren
APA
Chuet, Q., Dai, T., Ouyang, Q., & Pirot, F. (2026). New Bounds for Proper h‐Conflict‐Free Colorings. Random Structures & Algorithms, 68(2). https://doi.org/10.1002/rsa.70054
Vancouver
Chuet Q, Dai T, Ouyang Q, Pirot F. New Bounds for Proper h‐Conflict‐Free Colorings. Random Structures & Algorithms. 2026;68(2). doi:10.1002/rsa.70054
BibTeX
@article{Chuet2026,
author = {Chuet, Quentin and Dai, Tianjiao and Ouyang, Qiancheng and Pirot, François},
title = {New Bounds for Proper h‐Conflict‐Free Colorings},
journal = {Random Structures & Algorithms},
year = {2026},
volume = {68},
number = {2},
doi = {10.1002/rsa.70054}
}
EUVIMED