  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,
$\chi_{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.
