Hitting Sets and Colorings of Hypergraphs
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.
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}
}
EUVIMED