EUVIMEDEUVIMED entdecken
Crossref

New Bounds for Proper h‐Conflict‐Free Colorings

Quentin Chuet, Tianjiao Dai, Qiancheng Ouyang, François Pirot

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →