T-tone colorings of graphs

Abstract

A t-Tone coloring of a graph assigns t distinct colors to each vertex with vertices at distance d having fewer than d colors in common. The i-Tone chromatic number of a graph is the smallest number of colors used in all t-Tone colorings of that graph. We discuss bounds for this number, and we exactly determine the value for several of classes of graphs, including cycles and trees. Cubic graphs with 2-Tone chromatic number 5 are shown to be equivalent to graph covers of the Petersen graph. Properties of Petersen covers are analyzed. © 2018 Utilitas Mathematica Publishing Inc. All rights reserved.