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.

  • $\begingroup$ Thanks for your enlightening answer. The two notions are the same indeed. $\endgroup$ – Yann David Jun 10 '15 at 23:26
  • $\begingroup$ However, I am less convinced by your argument that conditions based on size alone cannot work, which seems to assume that bigger is necessarily better. Given a graph with a solution, I think one could characterize the structure of the vertices by enumerating the sizes of all possible vertex unions. The idea would then be to repeat the process on all solutions (up to a point where the existence of a solution would be obvious: each vertex would be larger than its degree, for instance). The task would be horrendous in practice! There must be a simpler way - if such systems can be any useful. $\endgroup$ – Yann David Jun 10 '15 at 23:48
  • $\begingroup$ @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) $\endgroup$ – Gregory J. Puleo Jun 11 '15 at 1:53
  • $\begingroup$ @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). $\endgroup$ – Gregory J. Puleo Jun 11 '15 at 2:10
  • $\begingroup$ You're right about systems diverging significantly from Hall's condition. Examining whether a given set of constraints works is hard indeed, but you wouldn't necessarily have to take that route to build a NASC (which would probably be sizable and difficult to build anyway - but on the other hand, even Hall's condition is not small, it can just be described elegantly). $\endgroup$ – Yann David Jun 11 '15 at 23:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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