A domination coloring of a graph G is a proper vertex coloring of G, such that each vertex of G dominates at least one color class (possibly its own class), and each color class is dominated by at least one vertex. The minimum number of colors among all domination colorings is called the domination chromatic number, denoted by ${\chi }_{dd}\left(G\right)$. In this paper, we study the complexity of the k-domination coloring problem by proving its NP-completeness for arbitrary graphs. We give basic results and properties of ${\chi }_{dd}\left(G\right)$, including the bounds and characterization results, and further research ${\chi }_{dd}\left(G\right)$ of some special classes of graphs, such as the split graphs, the generalized Petersen graphs, corona products, and edge corona products. Several results on graphs with ${\chi }_{dd}\left(G\right)=\chi \left(G\right)$ are presented. Moreover, an application of domination colorings in social networks is proposed.

The Total Coloring Conjecture (TCC) states that every simple graph G is totally $(\Delta +2)$-colorable, where $\Delta$ denotes the maximum degree of G. In this paper, we prove that TCC holds for dumbbell maximal planar graphs. Especially, we divide the dumbbell maximal planar graphs into three categories according to the maximum degree: $J_9$, I-dumbbell maximal planar graphs and II-dumbbell maximal planar graphs. We give the necessary and sufficient condition for I-dumbbell maximal planar graphs, and prove that any I-dumbbell maximal planar graph is totally 8-colorable. Moreover, a linear time algorithm is proposed to compute a total $(\Delta +2)$-coloring for any I-dumbbell maximal planar graph.