Keszegh–Pálvölgyi linear bound conjecture for polychromatic coloring
Keszegh–Pálvölgyi linear bound conjecture for polychromatic coloring
Let be a hereditary family of hypergraphs, and let be the least integer , if it exists, such that every -heavy member of is polychromatically -colorable; set if no such exists. A hypergraph is -heavy when every edge has size at least , and a coloring is polychromatic when every edge contains a vertex of each of the colors.
Keszegh–Pálvölgyi linear bound conjecture. For every and every hereditary family ,
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
Sign in to submit a solution.
No solutions have been posted yet.