Graph-Like Scheduling Problems and Property B

Breuer and Klivans defined a diverse class of scheduling problems in terms of Boolean formulas with atomic clauses that are inequalities. We consider what we call graph-like scheduling problems. These are Boolean formulas that are conjunctions of disjunctions of atomic clauses (𝑥 𝑖 ≠ 𝑥 𝑗 ). These problems generalize proper coloring in graphs and hypergraphs. We focus on the existence of a solution with all 𝑥 i taking the value of 0 or 1 (i.e. problems analogous to the bipartite case). When a graph-like scheduling problem has such a solution, we say it has property B just as is done for 2-colorable hypergraphs. We define the notion of a 𝜆-uniform graph-like scheduling problem for any integer partition 𝜆. Some bounds are attained for the size of the smallest 𝜆-uniform graph-like scheduling problems without B. We make use of both random and constructive methods to obtain bounds. Just as in the case of hypergraphs finding tight bounds remains an open problem.