Two generalizations of proper coloring: hardness and approximability
From MaRDI portal
Publication:6168932
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
Cites work
- An analysis of approximations for maximizing submodular set functions—I
- Approximation schemes for covering and packing problems in image processing and VLSI
- Exact exponential algorithms.
- Graph Classes: A Survey
- Graph-Theoretic Concepts in Computer Science
- Graph-Theoretic Concepts in Computer Science
- Maximum bipartite subgraph of geometric intersection graphs
- Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs
- Parameterized algorithms
- Polyhedral results for the bipartite induced subgraph problem
- 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)
