New results in $t$-tone coloring of graphs

Details New results in $t$-tone coloring of graphs New results in $t$-tone coloring of graphs

2011-08-24

arxiv.org/abs/1108.4751v1

Mathematics

Combinatorics

13 pages, 1 figure

Scientific paper

A $t$-tone $k$-coloring of $G$ assigns to each vertex of $G$ a set of $t$ colors from $\{1,..., k\}$ so that vertices at distance $d$ share fewer than $d$ common colors. The {\it $t$-tone chromatic number} of $G$, denoted $\tau_t(G)$, is the minimum $k$ such that $G$ has a $t$-tone $k$-coloring. Bickle and Phillips showed that always $\tau_2(G) \le [\Delta(G)]^2 + \Delta(G)$, but conjectured that in fact $\tau_2(G) \le 2\Delta(G) + 2$; we confirm this conjecture when $\Delta(G) \le 3$ and also show that always $\tau_2(G) \le \ceil{(2 + \sqrt{2})\Delta(G)}$. For general $t$ we prove that $\tau_t(G) \le (t^2+t)\Delta(G)$. Finally, for each $t\ge 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)} \le \tau_t(T) \le c_2\sqrt{\Delta(T)}$.

Affiliated with

Also associated with

No associations

Rating

New results in $t$-tone coloring of graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with New results in $t$-tone coloring of graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New results in $t$-tone coloring of graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-377069