# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Algorithmic Aspects of Dominator Colorings in Graphs

##### MPS-Authors

There are no MPG-Authors available

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Arumugam, S., Chandrasekar, K. R., Misra, N., Philip, G., & Saurabh, S. (2011).
Algorithmic Aspects of Dominator Colorings in Graphs. In C. S. Iliopoulos, & W. F. Smyth (*Combinatorial Algorithms* (pp. 19-30). Berlin: Springer. doi:10.1007/978-3-642-25011-8_2.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0019-DC20-A

##### Abstract

In this paper we initiate a systematic study of a problem that
has the flavor of two classical problems, namely \sc Coloring}
and {\sc Domination}, from the perspective of algorithms and
complexity. A {\it dominator coloring} of a graph G is an
assignment of colors to the vertices of G such that it is a
proper coloring and every vertex dominates all the vertices of
at least one color class. The minimum number of colors required
for a dominator coloring of G is called the {\it dominator
chromatic number} of G and is denoted by χ_d(G). In the
{\sc Dominator Coloring (DC)} problem, a graph G and a
positive integer k are given as input and the objective is to
check whether χ_d(G)≤q k. We first show that unless P=NP,
DC cannot be solved in polynomial time on bipartite, planar, or
split graphs.
This resolves an open problem posed by Chellali and Maffray
[{\it Dominator Colorings in Some Classes of Graphs, Graphs and
Combinatorics, 2011] about the polynomial time solvability of
DC on chordal graphs.
We then complement these hardness results by showing that the
problem is fixed parameter tractable (FPT) on chordal graphs and
in graphs which exclude a fixed apex graph as a
minor.