Keszegh–Pálvölgyi conjecture on 2-coloring one-headed directed hypergraphs
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.
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
Sign in to submit a solution.
No solutions have been posted yet.