1
$\begingroup$

I have a set of vertices $V$ such each vertex $v\in V$ is labelled with a color $col(v)$. I want to consider the class of partitions of $V$ that have the following property in common: all vertices having the same color must belong to the same part.

For example:

  1. Partition the vertices of $V$ according to their colors. $V(col)$ is a subset of vertices of $V$ whose color is $col$.

  2. Partition the vertices of $V$ according to the first letter of their color. $V(r)$ is the set of vertices of $V$ whose color starts with letter (r), for example (red).

  3. Partition the vertices of $V$ according to the number of the letters of their color. $V(4)$ is the set of vertices of $V$ whose colors have 4 letters (blue, ....).

I need a (concise) notation to describe the set of all these partitions. The notation have to give me access to the parameter of the partition, for example I need to be able to speak about $V(x)$ where $x$ may be a color, a first letter in a color, .... Thank you.

1 Answers 1

1

Let's say that such a partition of the vertices of $G$ respects colors.

If there are $n$ colors, the number of partitions that respect colors is $B_n$, the $n$-th Bell number. There is no nice closed form for the Bell numbers, but they grow rather quickly: starting with $B_0$, the first few are $1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147$, and $115975$. (This is sequence A000110 in the Online Encyclopedia of Integer Sequences). With only five colors you already have $52$ possible partitions.

Thus, it seems very likely that a partition that respects colors may not have its pieces determined by an identifiable parameter, unless the number of colors is very small, perhaps no more than four.