Given a graph and a partition of the vertices, an
independent transversal is a set
U of non-adjacent vertices such that each part contains exactly one vertex of
U. A strong coloring is equivalent to a partition of the vertices into disjoint independent-transversals (each independent-transversal is a single "color"). This is in contrast to
graph coloring, which is a partition of the vertices of a graph into a given number of
independent sets, without the requirement that these independent sets be transversals. To illustrate the difference between these concepts, consider a faculty with several departments, where the dean wants to construct a committee of faculty members. But some faculty members are in conflict and will not sit in the same committee. If the "conflict" relations are represented by the edges of a graph, then: • An
independent set is a committee with no conflict. • An
independent transversal is a committee with no conflict, with exactly one member from each department. • A
graph coloring is a partitioning of the faculty members into committees with no conflict. • A
strong coloring is a partitioning of the faculty members into committees with no conflict and with exactly one member from each department. Thus this problem is sometimes called the
happy dean problem. == References ==