Deciding Relaxed Two-Colourability: A Hardness Jump

DOI10.1017/S0963548309009663MaRDI QIDQ3557504zbMATH OpenOpenAlexFDO

Authors Robert Berke, Tibor Szabó

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

zbMATH Keywords

relaxationmonochromatic componentshardness jumpproper two coloringquasilinear time algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

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)

• Deciding Relaxed Two-Colorability—A Hardness Jump
• Splitting planar graphs of girth 6 into two linear forests with short paths
• Relaxed two-coloring of cubic graphs
• Relaxed two-coloring of cubic graphs
• On \(t\)-relaxed 2-distant circular coloring of graphs

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)