Inspired by graceful labelings and total labelings of graphs, we introduce the idea of total difference labelings. A $k$-total labeling of a graph $G$ is an assignment of $k$ distinct labels to the edges and vertices of a graph so that adjacent vertices, incident edges, and an edge and its incident vertices receive different labels. A $k$-total difference labeling of a graph $G$ is a function $f$ from the set of edges and vertices of $G$ to the set $\{1,2,\ldots,k\}$, that is a $k$-total labeling of $G$ and for which $f(\{u,v\})=|f(u)-f(v)|$ for any two adjacent vertices $u$ and $v$ of $G$ with incident edge $\{u,v\}$. The least positive integer $k$ for which $G$ has a $k$-total difference labeling is its total difference chromatic number, $χ_{td}(G)$. We determine the total difference chromatic number of paths, cycles, stars, wheels, gears and helms. We also provide bounds for total difference chromatic numbers of caterpillars, lobsters, and general trees.

18 pages, 11 figures