Two generalizations of proper coloring: hardness and approximability

DOI10.1007/978-3-031-22105-7_8OpenAlexW4313351200MaRDI QIDQ6168932

Ivan A. Bliznets, Danil Sagunov

Publication date: 10 August 2023

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

Full work available at URL: https://doi.org/10.1007/978-3-031-22105-7_8

zbMATH Keywords

graph algorithmscoloringapproximation algorithmsparameterized complexityexact algorithmsunit disk graphs

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• Exact exponential algorithms.
• Maximum bipartite subgraph of geometric intersection graphs
• Polyhedral results for the bipartite induced subgraph problem
• Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs
• Approximation schemes for covering and packing problems in image processing and VLSI
• An analysis of approximations for maximizing submodular set functions—I
• Graph Classes: A Survey
• Parameterized Algorithms
• Graph-Theoretic Concepts in Computer Science
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Two generalizations of proper coloring: hardness and approximability