## Abstract

We consider (not necessarily proper) colorings of the vertices of a graph where every color is thoroughly dispersed, 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 two has FTD(G) ≥ 3/2 and this is best possible. For planar graphs, we show that every triangular disc has FTD(G) ≥ 3/2 and this is best possible, and that every planar graph has td(G) ≤ 3/2 and this is best possible, while we conjecture that every planar triangulation has td(G) ≥ 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) ≥ 3/2 -0(1). We also consider the related concepts in hypergraphs.

Original language | English |
---|---|

Pages (from-to) | 174-191 |

Number of pages | 18 |

Journal | Journal of Graph Theory |

Volume | 88 |

Issue number | 1 |

DOIs | |

Publication status | Published - May 2018 |

## Keywords

- 05C15
- 05C69
- coloring
- thoroughly dispersed coloring
- total domination
- transversal

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Geometry and Topology