Paper detail

Thoroughly Distributed Colorings

We consider (not necessarily proper) colorings of the vertices of a graph where every color is thoroughly distributed, that is, appears in every open neighborhood. Equivalently, every color is a total dominating set. We define $\td(G)$ as the maximum number of colors in such a coloring and $\FTD(G)$ as the fractional version thereof. In particular, we show that every claw-free graph with minimum degree at least~$2$ has~$\FTD(G)\ge 3/2$ and this is best possible. For planar graphs, we show that every triangular disc has $\FTD(G) \ge 3/2$ and this is best possible, and that every planar graph has $\td(G) \le 4$ and this is best possible, while we conjecture that every planar triangulation has $\td(G)\ge 2$. Further, although there are arbitrarily large examples of connected, cubic graphs with $\td(G)=1$, we show that for a connected cubic graph $\FTD(G) \ge 2-o(1)$, and conjecture that it is always at least~$2$. We also consider the related concepts in hypergraphs.