Keszegh–Pálvölgyi conjecture on 2-coloring one-headed directed hypergraphs

From papers

Let H=(V,E)H=(V,E) be a directed hypergraph, with each hyperedge partitioned into head-vertices and tail-vertices; write h(e)h(e) and t(e)t(e) for the head and tail of a hyperedge ee. A proper 2-coloring is a coloring of the vertices with two colors such that every hyperedge contains vertices from at least two color classes.

Keszegh–Pálvölgyi conjecture. If every hyperedge has more tail-vertices than head-vertices, and for every e1,e2E(H)e_{1},e_{2}\in E(H) with e1e2=1|e_{1}\cap e_{2}|=1 the common vertex is a head-vertex of at least one of e1,e2e_{1},e_{2}, then HH admits a proper 2-coloring.

This conjecture generalizes Lovász's sufficient condition for proper 2-colorability of hypergraphs. The source states that it is proved in the special case where every hyperedge has exactly one head-vertex; in that case the size condition means that every hyperedge has at least two tail-vertices. The general conjecture remains unresolved in the supplied text.

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

Balázs István Szabó, “Coloring one-headed directed hypergraphs”, arXiv:2503.00189 (2025).

Solutions 0

No solutions have been posted yet.