Two generalizations of proper coloring: hardness and approximability
From MaRDI portal
Publication:6168932
DOI10.1007/978-3-031-22105-7_8OpenAlexW4313351200MaRDI QIDQ6168932FDOQ6168932
Authors: I. 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
Recommendations
- scientific article; zbMATH DE number 7561584
- The complexity of generalized graph colorings
- On the hardness of approximating the chromatic number
- Hardness of Approximate Hypergraph Coloring
- Conditional hardness for approximate coloring
- Conditional Hardness for Approximate Coloring
- On the complexity of injective colorings and its generalizations
- Polynomial-time approximation algorithms for the coloring problem in some cases
- Lower bounds on coloring numbers from hardness hypotheses in pcf theory
approximation algorithmsexact algorithmsgraph algorithmsparameterized complexitycoloringunit disk graphs
Cites Work
- Graph Classes: A Survey
- Exact exponential algorithms.
- Parameterized algorithms
- An analysis of approximations for maximizing submodular set functions—I
- Approximation schemes for covering and packing problems in image processing and VLSI
- Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs
- Graph-Theoretic Concepts in Computer Science
- Polyhedral results for the bipartite induced subgraph problem
- Graph-Theoretic Concepts in Computer Science
- Maximum bipartite subgraph of geometric intersection graphs
- Resolving conflicts for lower-bounded clustering
Cited In (2)
This page was built for publication: Two generalizations of proper coloring: hardness and approximability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6168932)
