Deciding Relaxed Two-Colourability: A Hardness Jump
From MaRDI portal
Publication:3557504
DOI10.1017/S0963548309009663zbMATH Open1209.05071OpenAlexW2137912301MaRDI QIDQ3557504FDOQ3557504
Publication date: 23 April 2010
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1017/s0963548309009663
Recommendations
- Deciding Relaxed Two-Colorability—A Hardness Jump
- Two generalizations of proper coloring: hardness and approximability
- scientific article
- ℋ-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
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
- A simplified NP-complete satisfiability problem
- Low diameter graph decompositions
- One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
- Fragmentability of graphs
- Efficient algorithms for Petersen's matching theorem
- On the bandwidth of triangulated triangles
- Partitioning into graphs with only small components
- Maximum acyclic and fragmented sets in regular graphs
- Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5
- Relaxed two-coloring of cubic graphs
- Bounded size components -- partitions and transversals.
- Relaxed chromatic numbers of graphs
Cited In (3)
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)
