New results in \(t\)-tone coloring of graphs

Daniel Cranston ; Jaehoon Kim ; William Kinnersley

The electronic journal of combinatorics, Tome 20 (2013) no. 2

Résumé

A $t$-tone $k$-coloring of $G$ assigns to each vertex of $G$ a set of $t$ colors from $\{1,\dots,k\}$ so that vertices at distance $d$ share fewer than $d$ common colors. The $t$-tone chromatic number of $G$, denoted $t(G)$, is the minimum $k$ such that $G$ has a $t$-tone $k$-coloring. Bickle and Phillips showed that always $\tau_2(G) \leq [\Delta(G)]^2 +\Delta(G)$, but conjectured that in fact $\tau_2(G) \leq 2\Delta(G) + 2$; we confirm this conjecture when $\Delta(G) \leq 3$ and also show that always $\tau_2(G) \leq \lceil (2 +\sqrt{2}) \Delta(G) \rceil$. For general $t$ we prove that $\tau_t(G) \leq (t^2+t) \Delta(G)$. Finally, for each $t \geq 2$ we show that there exist constants $c_1$ and $c_2$ such that for every tree $T$ we have $c_1 \sqrt{\Delta(T)} \leq \tau_t(T) \leq c_2\sqrt{\Delta(T)}$.

Détail

DOI : 10.37236/2710

Classification : 05C05, 05C15
Mots-clés : \(t\)-tone chromatic number