Algorithmic aspects of dominator colorings in graphs

DOI10.1007/978-3-642-25011-8_2MaRDI QIDQ3111637zbMATH OpenOpenAlexFDO

Authors S. Arumugam, K. Raja Chandrasekar, Neeldhara Misra, Geevarghese Philip, Saket Saurabh

Publication date 13 January 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-25011-8_2

zbMATH Keywords

apex-minor-free graphschordal graphsdominator coloringfixed-parameter tractability

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Dominator colorings in some classes of graphs
• An algorithm for the dominator chromatic number of a tree
• Dominated colorings of graphs
• On the double total dominator chromatic number of graphs
• On dominator colorings in graphs

Cited in

(32)

• On the number of maximal independent sets in minimum colorings of split graphs
• On the complexity of minimum \(q\)-domination partization problems
• On the complexity of cd-coloring of graphs
• Dominated colorings of graphs
• An algorithm for the dominator chromatic number of a tree
• On some domination colorings of graphs
• Parameterized and exact algorithms for class domination coloring
• On the dominator coloring in proper interval graphs and block graphs
• The cd-coloring of graphs
• Parameterized and exact algorithms for class domination coloring
• A lower bound of the cd-chromatic number and its complexity
• Dominator and total dominator colorings in graphs
• Dominator colorings and safe clique partitions
• On dominator colorings in graphs
• Matched-Factor d-Domatic Coloring of Graphs
• On strict strong coloring of graphs
• Dominator and total dominator coloring of circulant graph C_n(1, 2)
• On the double total dominator chromatic number of graphs
• Linear time algorithm for dominator chromatic number of trestled graphs
• Lower bounds on approximating some variations of vertex coloring problem over restricted graph classes
• A color-to-spin domino Schensted algorithm
• On cd-coloring of \(\{P_5,K_4\}\)-free chordal graphs
• On CD-chromatic number and its lower bound in some classes of graphs
• Dominator coloring and CD coloring in almost cluster graphs
• Complexity of total dominator coloring in graphs
• Approximation algorithm for minimum \(q\)-dominator partization problem
• Dissimilarity between dominator and total dominator coloring of certain graphs
• On dominator coloring of corona products of some generalized graphs
• Dominator coloring and CD coloring in almost cluster graphs
• A reinforced system for the Playfair cipher by incorporating dominator coloring in Latin square graphs
• On dominator coloring in Mycielskian graphs
• On cd-coloring of trees and co-bipartite graphs

This page was built for publication: Algorithmic aspects of dominator colorings in graphs

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