Parameterized and Exact Algorithms for Class Domination Coloring

DOI10.1007/978-3-319-51963-0_26zbMath1444.68147arXiv2203.09106OpenAlexW2571262586MaRDI QIDQ2971145

R. Krithika, Saket Saurabh, Ashutosh Rai, Prafullkumar Tale

Publication date: 4 April 2017

Published in: SOFSEM 2017: Theory and Practice of Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (8)

On the complexity of minimum \(q\)-domination partization problems ⋮ On cd-coloring of trees and co-bipartite graphs ⋮ On the complexity of cd-coloring of graphs ⋮ On cd-coloring of \(\{P_5,K_4\}\)-free chordal graphs ⋮ On CD-chromatic number and its lower bound in some classes of graphs ⋮ A Lower Bound of the cd-Chromatic Number and Its Complexity ⋮ On the algorithmic aspects of strong subcoloring ⋮ Lower bounds on approximating some variations of vertex coloring problem over restricted graph classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
• Fundamentals of parameterized complexity
• Exact algorithms for dominating set
• Dominator colorings in some classes of graphs
• Improved upper bounds for vertex cover
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• Parameterized approximation of dominating set problems
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• The maximum k-colorable subgraph problem for chordal graphs
• The node-deletion problem for hereditary properties is NP-complete
• A note on the complexity of the chromatic number problem
• The complexity of generalized clique covering
• Parameterized complexity of vertex colouring
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Fast multiplication of large numbers
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The cd-Coloring of Graphs
• Set Partitioning via Inclusion-Exclusion
• Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Faster Parameterized Algorithms Using Linear Programming
• B-chromatic number: Beyond NP-hardness
• Parameterized Algorithms

This page was built for publication: Parameterized and Exact Algorithms for Class Domination Coloring