English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Algorithmic Aspects of Dominator Colorings in Graphs

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 (Eds.), Combinatorial Algorithms (pp. 19-30). Berlin: Springer. doi:10.1007/978-3-642-25011-8_2.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-DC20-A Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-DC21-8
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Arumugam, S.1, Author
Chandrasekar, K. Raja1, Author
Misra, Neeldhara1, Author
Philip, Geevarghese1, Author           
Saurabh, Saket1, Author
Affiliations:
1External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 20112011
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: DOI: 10.1007/978-3-642-25011-8_2
BibTex Citekey: arumugamchandrasekarmisraphilipsaurabh2011
 Degree: -

Event

show
hide
Title: IWOCA 2011
Place of Event: Victoria, Canada
Start-/End Date: 2011-07-20 - 2011-07-22

Legal Case

show

Project information

show

Source 1

show
hide
Title: Combinatorial Algorithms
  Abbreviation : IWOCA 2011
  Subtitle : 22nd International Workshop, IWOCA 2011, Victoria, BC, Canada, July 20-22, 2011, Revised Selected Papers
Source Genre: Proceedings
 Creator(s):
Iliopoulos, Costas S.1, Editor
Smyth, William F.1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 19 - 30 Identifier: ISBN: 978-3-642-25010-1

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 7056 Sequence Number: - Start / End Page: - Identifier: -