We are given finite sets $A$ and $B$ and a set $S\subseteq \mathcal{P}(A)$. The members of $\mathcal{S}$ may have arbitrary intersections with one another and their union is not necessarily $A$. We wish to determine whether there is a function $A\to B$ so that no member of $B$ is the image of more than $k$ members of any $T\in S$.


1 Answer 1


This is an example of a constraint satisfaction problem. The variables of the problem are the "colors" of the elements of $A$, where $B$ is the set of colors. For each set $T \in S$ and each $(k+1)$-subset $T'$ of $T$, there is a constraint stating that the elements of $T'$ cannot all have the same color.

If $k=1$ and all $T \in S$ have cardinality $2$, then this is just graph coloring. You can similarly put graph hypercoloring in this framework.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.