Chromatic Spectrum of $K_s$-WORM Colorings of $K_n$

Abstract

An {\it $H$-WORM} coloring of a simple graph $G$ is the coloring of the vertices of $G$ such that no copy of $H\subseteq G$ is monochrome or rainbow. In a recently published article by one of the authors \cite{All1}, it was claimed that the number of $r$-partitions in a $K_s$-WORM coloring of $K_n$ is $ \zeta_r=\stirr{n}{r}$, where $\stirr{n}{r}$ denotes the Stirling number of the second kind, for all $3\le r\le s < n$. We found that $ \displaystyle \zeta_r = \stirr{n}{r}$ if and only if ${\lceil \frac{n+3}{2} \rceil}<s\le n$ with $r<s$. Further investigations into $\zeta_2$, given any $K_3$-WORM coloring of $K_n$, show its relation with the number of spanning trees of cacti and the Catalan numbers. Moreover, we extend the notion of $H$-WORM colorings to $(H_1;H_2)$-\textit{mixed} colorings, where $H_1$ and $H_2$ are distinct subgraphs of $G$; these coloring constraints are closely related to those of mixed hypergraph colorings.

Keywords

• catalan numbers
• chromatic spectrum
• mixed hypergraph coloring
• stirling numbers