Deciding Relaxed Two-Colourability: A Hardness Jump
From MaRDI portal
Publication:3557504
DOI10.1017/S0963548309009663zbMath1209.05071OpenAlexW2137912301MaRDI QIDQ3557504
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
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (2)
Relaxed two-coloring of cubic graphs ⋮ Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths
Cites Work
- A simplified NP-complete satisfiability problem
- 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
- Low diameter graph decompositions
- Relaxed chromatic numbers of graphs
- Bounded size components -- partitions and transversals.
- Partitioning into graphs with only small components
- On the bandwidth of triangulated triangles
- Fragmentability of graphs
- Efficient Algorithms for Petersen's Matching Theorem
- Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
- One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
- Maximum acyclic and fragmented sets in regular graphs
This page was built for publication: Deciding Relaxed Two-Colourability: A Hardness Jump
