Keszegh–Pálvölgyi conjecture on 2-coloring one-headed directed hypergraphs
Let be a directed hypergraph, with each hyperedge partitioned into head-vertices and tail-vertices; write and for the head and tail of a hyperedge . 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 with the common vertex is a head-vertex of at least one of , then 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
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.