Thoroughly dispersed colorings

Wayne Goddard, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)

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 languageEnglish
Pages (from-to)174-191
Number of pages18
JournalJournal of Graph Theory
Volume88
Issue number1
DOIs
Publication statusPublished - May 2018

Keywords

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

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Geometry and Topology

Fingerprint

Dive into the research topics of 'Thoroughly dispersed colorings'. Together they form a unique fingerprint.

Cite this