# Generalizing Hall's marriage theorem to arbitrary graphs

Given a finite graph G = (V, E) in which each vertex is a finite set, I call system of local representatives the choice for each vertex of one of its elements (the local representative), so that no two adjacent vertices have the same local representative. Hall's theorem corresponds to the case where the graph is a clique and representatives are globally unique.

I wonder how to build a minimal / minimum system of constraints on the sizes of the vertices (and those of their unions - in the style of Hall's theorem) that would provide a necessary and sufficient condition for the existence of a set of local representatives. The construction would ideally be simple and fast (relatively to the size of the constraint set).

I am under the impression that there is always such a system of constraints, but even that is not in fact completely obvious.

Example: G = ({a, b, c}, {(a, b), (b,c)}) → a–b–c

I believe that the following system works: |a| ≥ 1 and |b| ≥ 1 and |c| ≥ 1 and |a ∪ b| ≥ 2 and |b ∪ c| ≥ 2 and not (|a| = 1 and |c| = 1 and |a ∪ c| = 2 and |b| = 2 and |a ∪ b ∪ c| = 2)

Any ideas, suggestions, pointers?

What you've invented is exactly the notion of list coloring: given a list $L(v)$ for each vertex $v$, we want to give each vertex $v$ a color from $L(v)$ such that adjacent vertices have different colors. Since classical graph coloring is hard (where $L(v) = \{1,\ldots,k\}$ for all $v$), most problems involving list coloring are also hard.
Edit: In particular, list coloring works in sometimes counterintuitive ways that suggests that necessary-and-sufficient conditions of the form you want (lower bounds on the sizes of lists and their unions) cannot work. Consider the complete bipartite graph $K_{3,3}$. This graph is bipartite, so it can be properly colored if $L(v) = \{1,2\}$ for all $v$. On the other hand, if you give the vertices on one side the lists $\{1,2\}, \{1,3\}, \{2,3\}$ and give the same lists to the vertices on the other side, then it's not difficult to see that no proper coloring exists. But, this bad list assignment has all lists, and all unions of lists, at least as big as the lists and unions in the good list assignment of $\{1,2\}$ everywhere.
• @YannDavid -- the assumption that "bigger is better" seemed to be implicit in your question and example, since the clause "not($|a| =1$ and...)" is equivalent, in conjunction with the other clauses, to "(|a| >= 2 or ...)". Dropping the "bigger is better" assumption loses a lot of the feel of Hall's condition, I think. (1/2) – Gregory J. Puleo Jun 11 '15 at 1:53
• @YannDavid also, note that, given $G$, even determining whether the constraints "all lists have size $3$ and all their unions have size $3$" allows for a good coloring is NP-hard, since that's just the $3$-colorability problem. so, that suggests that there's no good way of generating the constraints (or at least, you sometimes need a huge set of constraints to get a NASC). – Gregory J. Puleo Jun 11 '15 at 2:10