[Submitted on 21 Jun 2026]

View PDF

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 $$ \bigl| N(v) \cap V_i \bigr|= \begin{cases}
\alpha°(v) & \text{if } v\notin V_i,\\[4pt]
\beta°(v) & \text{if } v\in V_i . \end{cases} $$
\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.

Submission history

From: Saeed Shaebani [view email]
[v1] Sun, 21 Jun 2026 07:49:39 UTC (8 KB)

Current browse context:

math.CO

Bookmark

Bibliographic and Citation Tools

Code, Data and Media Associated with this Article

Demos

Recommenders and Search Tools

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.