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