EUVIMEDEUVIMED entdecken
Crossref

Hitting Sets and Colorings of Hypergraphs

Balázs Bursics, Bence Csonka, Luca Szepessy

SIAM Journal on Discrete Mathematics · 30.09.2026 · 40 (3) · 1123-1140

DOI: 10.1137/23m1615796 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 21.07.2026. Verfasst von Balázs Bursics und 2 weiteren Autor:innen. Die Arbeit nennt 24 Literaturangaben. Gefördert von: Magyar Tudományos Akadémia, Hungarian Academy of Sciences.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In this paper, we study the minimal size of edges in hypergraph families that guarantees the existence of a polychromatic coloring, that is, a [Formula: see text]-coloring of a vertex set such that every hyperedge contains a vertex of all [Formula: see text] color classes. We also investigate the connection of this problem with [Formula: see text]-shallow hitting sets: sets of vertices that intersect each hyperedge in at least one and at most [Formula: see text] vertices. We determine for some hypergraph families the minimal [Formula: see text] for which a [Formula: see text]-shallow hitting set exists. We also study this problem for a special hypergraph family, which is induced by arithmetic progressions with a difference from a given set. We show connections between some geometric hypergraph families and the latter, and we prove relations between the set of differences and polychromatic colorability.

Förderung

  • Magyar Tudományos Akadémia
  • Hungarian Academy of Sciences

Zitieren

APA

Bursics, B., Csonka, B., & Szepessy, L. (2026). Hitting Sets and Colorings of Hypergraphs. SIAM Journal on Discrete Mathematics, 40(3), 1123-1140. https://doi.org/10.1137/23m1615796

Vancouver

Bursics B, Csonka B, Szepessy L. Hitting Sets and Colorings of Hypergraphs. SIAM Journal on Discrete Mathematics. 2026;40(3):1123-1140. doi:10.1137/23m1615796

BibTeX
@article{Bursics2026,
  author = {Bursics, Balázs and Csonka, Bence and Szepessy, Luca},
  title = {Hitting Sets and Colorings of Hypergraphs},
  journal = {SIAM Journal on Discrete Mathematics},
  year = {2026},
  volume = {40},
  number = {3},
  pages = {1123--1140},
  doi = {10.1137/23m1615796}
}
Kostenlos starten →