On The Number of Irreducible FAT Colorings

Abstract

A vertex coloring of a graph $G$ with nonempty color classes $V_1,V_2,\dots ,V_k$ is called a \emph{FAT $k$-coloring} if there exist real numbers $\alpha ,\beta \in [0,1]$ such that for every vertex $v$ and every color class $V_i\in \left\{V_1,V_2,\dots ,V_k\right\}$ we have $$|N(v)\cap V_i|=\{\begin{array}{ll}\alpha °(v)& \text{if }v\notin V_i,\\ \beta °(v)& \text{if }v\in V_i.\end{array}$$ \noindent The FAT coloring concept was originally proposed and thoroughly studied by Beers and Mulas. The set of all FAT colorings of a graph is naturally ordered by the coarsening relation, in which finer partitions are larger in the order. The maximal elements of this poset, called \emph{irreducible FAT colorings}, form a generating set: every FAT coloring of the graph can be obtained by merging color classes of some irreducible one. Beers and Mulas raised the compelling question whether, for every positive integer $s$, there exists a graph that admits exactly $s$ irreducible FAT colorings. In this paper we settle this question affirmatively by exhibiting, for any given $s$, a graph possessing precisely $s$ such colorings.