Deciding Relaxed Two-Colourability: A Hardness Jump
From MaRDI portal
Publication:3557504
Recommendations
- Deciding Relaxed Two-Colorability—A Hardness Jump
- Two generalizations of proper coloring: hardness and approximability
- scientific article; zbMATH DE number 68352
- ℋ-Colouring Dichotomy in Proof Complexity
- Deciding hypergraph 2-colourability by H-resolution
- Lower bounds on coloring numbers from hardness hypotheses in pcf theory
- Two cases of polynomial-time solvability for the coloring problem
- NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
- Conditional hardness for approximate coloring
- Conditional Hardness for Approximate Coloring
Cites work
- A simplified NP-complete satisfiability problem
- Bounded size components -- partitions and transversals.
- Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
- Efficient algorithms for Petersen's matching theorem
- Fragmentability of graphs
- Low diameter graph decompositions
- Maximum acyclic and fragmented sets in regular graphs
- On the bandwidth of triangulated triangles
- One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
- Partitioning into graphs with only small components
- Relaxed chromatic numbers of graphs
- Relaxed two-coloring of cubic graphs
- Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5
Cited in
(5)
This page was built for publication: Deciding Relaxed Two-Colourability: A Hardness Jump
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3557504)