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

About 1 year old · traced to

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,e2∈E(H)e_{1},e_{2}\in E(H) with ∣e1∩e2∣=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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.