Lower bounds on approximating some variations of vertex coloring problem over restricted graph classes

DOI10.1142/S179383092050086XzbMath1458.05061OpenAlexW3040538529MaRDI QIDQ5859496

Sounaka Mishra, Sayani Das

Publication date: 16 April 2021

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s179383092050086x

zbMATH Keywords

graph algorithmschordal graphvertex coloringweakly chordal graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items

On the complexity of minimum \(q\)-domination partization problems ⋮ On cd-coloring of \(\{P_5,K_4\}\)-free chordal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On dominator colorings in graphs
• Dominator colorings in some classes of graphs
• Dominator coloring of generalized Petersen graphs
• Optimizing weakly triangulated graphs
• On the complexity of cd-coloring of graphs
• Dominated colorings of graphs
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Parameterized and Exact Algorithms for Class Domination Coloring
• Algorithmic Aspects of Dominator Colorings in Graphs
• A threshold of ln n for approximating set cover