Here are some ways to generalize the notion of a bipartite graph to hypergraphs:
-
A hypergraph is called 2-colorable if its vertices can be 2-colored such that each hyperedge of size at least 2 contains at least one vertex of each color.
-
A hypergraph is called exactly-2-colorable if its vertices can be 2-colored such that each hyperedge contains exactly one green vertex.
-
A hypergraph is called balanced if every restriction of it to a subset of the vertices is 2-colorable. I.e., it remains 2-colorable upon removing any subset of vertices from it.
For simple graphs, all these properties are equivalent to bipartiteness, but for general hypergraphs they are different. My question is what is the relation between them – which of them is the strongest? So far I found the following:
-
Exact-2-colorability is strictly stronger than 2-colorability. For example, the hypergraph { {1,2,3} , {1,2,4} , {1,3,4} , {2,3,4} } is 2-colorable e.g. by coloring 1,2 green and 3,4 blue, but it is not exactly-2-colorable.
-
Balancedness is strictly stronger than 2-colorability. For example, the above hypergraph is not balanced, since upon removing the vertex 1 it becomes the hypergraph { {2,3} , {2,4} , {3,4} , {2,3,4} }, which is not 2-colorable as it contains an odd-length cycle.
-
Exact-2-colorability does not imply balancedness. For example, the hypergraph { {1,2,3} , {1,2,4} , {1,3,4} } is exactly-2-colorable, e.g. by coloring green only the vertex 1. But it is not balanced, since upon removing the vertex 1 it becomes an odd-length cycle.
But, does balancedness imply exact-2-colorability? Is it true that every balanced hypergraph is also exactly-2-colorable?
Best Answer
Here are three examples of balanced hypergraphs which are not exactly-$2$-colorable. (As they are all quite trivial, they probably just show that I don't understand the definitions, or the definitions were imprecisely formulated.)
$H_1=\{\emptyset\}$.
$H_2=\{\{1\},\{2\},\{1,2\}\}$.
$H_3=\{\{1,2\},\{3,4\},\{1,2,3,4\}\}$.