Keszegh–Pálvölgyi linear bound conjecture for polychromatic coloring

From papers

Let F\mathcal F be a hereditary family of hypergraphs, and let mk(F)m_k(\mathcal F) be the least integer mm, if it exists, such that every mm-heavy member of F\mathcal F is polychromatically kk-colorable; set mk(F)=m_k(\mathcal F)=\infty if no such mm exists. A hypergraph is mm-heavy when every edge has size at least mm, and a coloring is polychromatic when every edge contains a vertex of each of the kk colors.

Keszegh–Pálvölgyi linear bound conjecture. For every kk and every hereditary family F\mathcal F,

mk(F)(k1)(m2(F)1)+1.m_k(\mathcal F)\le (k-1)(m_2(\mathcal F)-1)+1.

This is a stronger quantitative form of the finiteness conjecture and was conjectured by Keszegh and the author. The paper states that it is disproved by a 5-uniform hypergraph with no polychromatic 3-coloring, although all its restricted subhypergraphs with edges of size at least 3 are 2-colorable.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Dömötör Pálvölgyi, “Note on polychromatic coloring of hereditary hypergraph families”, arXiv:2309.04603 (2023).

Solutions 0

No solutions have been posted yet.