Complexity of total dominator coloring in graphs

DOI10.1007/S00373-023-02726-9MaRDI QIDQ6184152zbMATH OpenOpenAlexFDO

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

Publication date 5 January 2024

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2303.01746

zbMATH Keywords

chordal graphsplanar graphsbipartite graphscographstotal dominator coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Abstract: Let $G=(V,E)$ be a graph with no isolated vertices. A vertex $v$ totally dominate a vertex $w$ ($wev$), if $v$ is adjacent to $w$. A set $DsubseteqV$ called a total dominating set of $G$ if every vertex $vinV$ 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 $gamm{a}_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 $ch{i}_{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 $ch{i}_{td}(T)=gamm{a}_t(T)+1$, which completes the characterization of trees achieving all possible values of $ch{i}_{td}(T)$. Also, we show that for a cograph $G$, $ch{i}_{td}(G)$ can be computed in linear-time. Moreover, we show that $2lech{i}_{td}(G)le4$ for a chain graph $G$ and give characterization of chain graphs for every possible value of $ch{i}_{td}(G)$ in linear-time.

Recommendations

• Total dominator colorings and total domination in graphs
• Dominator and total dominator colorings in graphs
• Algorithmic aspects of dominator colorings in graphs
• On dominator colorings in graphs
• scientific article; zbMATH DE number 2170484
• Publication:4725766
• Coloring and domination in graphs
• The complexity of some graph colouring problems
• The complexity of generalized graph colorings
• COLORING AND GLOBAL DOMINATION IN GRAPHS

Cites work

• scientific article; zbMATH DE number 2044943 (Why is no real title available?)
• Algorithmic aspects of dominator colorings in graphs
• Approximation hardness of dominating set problems in bounded degree graphs
• Domination in Graphs: Core Concepts
• Dominator and total dominator colorings in graphs
• Dominator partitions of graphs
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• On a property of the class of n-colorable graphs
• On dominator colorings in graphs
• Structures of domination in graphs
• Topics in Domination in Graphs
• Total domination in graphs
• Total dominator chromatic number of Mycieleskian graphs
• Total dominator chromatic number of a graph
• Total dominator coloring in product graphs
• Total dominator coloring of circulant graphs C_n(a,b)
• Total dominator colorings and total domination in graphs
• Total dominator colorings in caterpillars
• Total dominator colorings in cycles
• Total dominator colorings in paths

Cited in

(4)

• On the complexity of cd-coloring of graphs
• Parameterized and exact algorithms for class domination coloring
• The complexity of the \(T\)-coloring problem for graphs with small degree
• An extensive study on the k-tuple total dominator chromatic number of graphs

This page was built for publication: Complexity of total dominator coloring in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6184152)