Premium
Thoroughly dispersed colorings
Author(s) -
Goddard Wayne,
Henning Michael A.
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22204
Subject(s) - combinatorics , mathematics , planar graph , edge coloring , list coloring , cubic graph , conjecture , graph , planar straight line graph , fractional coloring , discrete mathematics , complete coloring , outerplanar graph , graph coloring , 1 planar graph , graph power , line graph , pathwidth , voltage graph
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 ) ≤ 4 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 ) ≥ 2 − o ( 1 ) . We also consider the related concepts in hypergraphs.