2-tone coloring of graphs with maximum degree 4

Abstract

A t-tone k-coloring of a graph G assigns to each vertex of G a set of t colors from {1,... ,k} such that vertices at distance d share fewer than d common colors. In particular, a 1-tone coloring is a proper vertex coloring. The t-chromatic number of G, denoted τt(G), is the minimum k such that G has a t-tone k-coloring. Cranston, Kim, and Kinnersley showed that if (G) < 3, then τ2(G) < 8. In this paper we show that if (G) < 4, then t2(G) < 12. © 2018 Utilitas Mathematica Publishing Inc. All rights reserved.