Note on Polychromatic Coloring of Hereditary Hypergraph Families

We exhibit a 5-uniform hypergraph that has no polychromatic 3-coloring, but all its restricted subhypergraphs with edges of size at least 3 are 2-colorable. This disproves a bold conjecture of Keszegh and the author, and can be considered as the first step to understand polychromatic colorings of hereditary hypergraph families better since the seminal work of Berge. We also show that our method cannot give hypergraphs of arbitrary high uniformity, and mention some connections to panchromatic colorings.

Authors

Institutions

Publication Details

Journal
Graphs and Combinatorics
Published
2024-11-22
DOI
https://doi.org/10.1007/s00373-024-02836-y
Primary Topic
Advanced Topology and Set Theory
Type
article
Field-Weighted Citation Impact
0.00

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Note on Polychromatic Coloring of Hereditary Hypergraph Families

Dömötör Pálvölgyi
Graphs and Combinatorics
Advanced Topology and Set Theory
article

Note on Polychromatic Coloring of Hereditary Hypergraph Families

Dömötör Pálvölgyi
article en

Abstract

We exhibit a 5-uniform hypergraph that has no polychromatic 3-coloring, but all its restricted subhypergraphs with edges of size at least 3 are 2-colorable. This disproves a bold conjecture of Keszegh and the author, and can be considered as the first step to understand polychromatic colorings of hereditary hypergraph families better since the seminal work of Berge. We also show that our method cannot give hypergraphs of arbitrary high uniformity, and mention some connections to panchromatic colorings.

Graphs and CombinatoricsVol. 40(6)
Eötvös Loránd University (HU), HUN-REN Alfréd Rényi Institute of Mathematics (HU)
Magyar Tudományos Akadémia, Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, National Research, Development and Innovation Office, HORIZON EUROPE European Research Council
Openalex Percentile: Top 68%
Advanced Topology and Set Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.