Graphs where every vertex is connected to a vertex of each other color/label

Question

What do you call a type of vertex labeling in which each vertex is connected to a vertex of every other label? (Two adjacent vertices are allowed to have the same label so it's not technically a coloring.)

So if the vertices are labeled $1$–$3$, all vertices labeled $1$ must be adjacent to at least one "$2$" vertex and at least one "$3$" vertex.

Alternately, you could see this as a graph invariant: for a given graph, what is the largest number of labels such that there is such a vertex labeling? Of course this could be at most one more than the minimum degree of the graph.

Answer 1

You are looking for a partitioning of the vertex set into a maximum number of dominating sets. That is, every color class has to be a dominating set, i.e., each vertex must see at least one of each color different from its own in its neighborhood.

This problem or invariant is known as domatic number, and it has been quite heavily studied. It's well-known to be NP-complete, and there are many algorithmic and combinatorial results for it.

If you insist that each vertex sees every color in its neighborhood (including its own), you are looking at the total domatic number, i.e., a partition of the vertex set into total dominating sets.

Answer 2

This problem is similar to finding the achromatic number $\psi(G)$ of a graph, and even more similar to finding the pseudoachromatic number $\Psi(G)$.

Both of these problems share the unusual property with your problem of trying to maximize the number of colors used. The achromatic number of $G$ is the maximum number of colors in a proper coloring where, for any two colors $i$ and $j$, there is an edge joining a vertex of color $i$ to a vertex of color $j$. The pseudoachromatic number of $G$ is defined similarly, except that the coloring no longer needs to be proper.

The pseudoachromatic number is most similar to the number defined in this question, except that not every vertex needs to have a neighbor in every other color class. It's enough that any two color classes have one edge between them. The pseudoachromatic number is an upper bound on the number in this question, though it's hard to say how it compares to the trivial bound of $\delta(G)+1$.

The achromatic number of a graph is defined by Harary and Hedetniemi in their paper with the obvious title, and the pseudoachromatic number in Gupta's Bounds on the chromatic and achromatic numbers of complementary graphs. One might look for any discussion of the problem in this question among the papers citing one of these two. I haven't found any, but I haven't gone to the extreme step of looking through all such papers.