Complexity of Total Dominator Coloring in Graphs

Michael A. Henning, Kusum, Arti Pandey, Kaustav Paul

Research output: Contribution to journalArticlepeer-review


Let G= (V, E) be a graph with no isolated vertices. A vertex v totally dominates a vertex w (w≠ v), if v is adjacent to w. A set D⊆ V called a total dominating set of G if every vertex v∈ V is totally dominated by some vertex in D. The minimum cardinality of a total dominating set is the total domination number of G and is denoted by γt(G) . A total dominator coloring of graph G is a proper coloring of vertices of G, so that each vertex totally dominates some color class. The total dominator chromatic number χtd(G) of G is the least number of colors required for a total dominator coloring of G. The Total Dominator Coloring problem is to find a total dominator coloring of G using the minimum number of colors. It is known that the decision version of this problem is NP-complete for general graphs. We show that it remains NP-complete even when restricted to bipartite, planar and split graphs. We further study the Total Dominator Coloring problem for various graph classes, including trees, cographs and chain graphs. First, we characterize the trees having χtd(T) = γt(T) + 1 , which completes the characterization of trees achieving all possible values of χtd(T) . Also, we show that for a cograph G, χtd(G) can be computed in linear-time. Moreover, we show that 2 ≤ χtd(G) ≤ 4 for a chain graph G and then we characterize the class of chain graphs for every possible value of χtd(G) in linear-time.

Original languageEnglish
Article number128
JournalGraphs and Combinatorics
Issue number6
Publication statusPublished - Dec 2023


  • Bipartite graphs
  • Chordal graphs
  • Cographs
  • Planar graphs
  • Total dominator coloring

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Complexity of Total Dominator Coloring in Graphs'. Together they form a unique fingerprint.

Cite this