Total dominator colorings and total domination in graphs (Q2354609)

Given a graph \(G\), a total dominator coloring is a proper coloring of the vertices of \(G\) in which each vertex is adjacent to every vertex of some color class. The total dominator chromatic number \(\chi_{d}^{t}(G)\) of \(G\) is the minimum number of colors among all total dominator colorings of \(G\). A total dominating set of \(G\) is a set \(S\) of vertices such that every vertex in \(G\) is adjacent to at least one vertex in \(S\). The total domination number \(\gamma_{t}(G)\) is the minimum cardinality of a total dominating set of \(G\). The author shows that every graph \(G\) with no isolated vertex satisfies \(\gamma_{t}(G) \leq \chi_{d}^{t}(G) \leq \gamma_{t}(G) + \chi(G)\), where \(\chi(G)\) denotes the chromatic number of \(G\). He establishes properties of total dominator colorings in trees, and characterizes those trees \(T\) for which \(\gamma_{t}(T) = \chi_{d}^{t}(T)\). Finally, he proves that if \(T\) is a tree of \(n \geq 2\) vertices, then \(\chi_{d}^{t}(T) \leq 2(n+1)/3\), and he characterizes those trees achieving equality in this bound.