Constructive generation of very hard 3-colorability instances
DOI10.1016/J.DAM.2006.07.015zbMATH Open1130.05058OpenAlexW2000872069MaRDI QIDQ2467358FDOQ2467358
Seiichi Nishihara, Kazunori Mizuno
Publication date: 21 January 2008
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2006.07.015
Recommendations
- Using Hajós’ Construction to Generate Hard Graph 3-Colorability Instances
- Constructions of 3-Colorable Cores
- The hardness of 3-uniform hypergraph coloring
- An intractability result for the vertex 3-colourability problem
- The complexity of some problems related to GRAPH 3-COLORABILITY
- On the Hardness of 4-Coloring a 3-Colorable Graph
- scientific article; zbMATH DE number 1463391
- 3-colorability of pseudo-triangulations
- Hardness results for three kinds of colored connections of graphs
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Consistency in networks of relations
- Title not available (Why is that?)
- Frozen development in graph coloring
- Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
- New methods to color the vertices of a graph
- The hardest constraint problems: A double phase transition
- Title not available (Why is that?)
- Title not available (Why is that?)
- Local optima topology for the \(k\)-coloring problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the Hardness of 4-Coloring a 3-Colorable Graph
- Exploiting the deep structure of constraint problems
Cited In (9)
- Expected polynomial-time randomized algorithm for graph coloring problem
- Proper colorability of segment intersection graphs
- Graphs with large girth and chromatic number are hard for Nullstellensatz
- Proper colorability of segment intersection graphs
- Low degree Nullstellensatz certificates for 3-colorability
- Regular pattern-free coloring
- Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
- Using Hajós’ Construction to Generate Hard Graph 3-Colorability Instances
- An incremental search heuristic for coloring vertices of a graph
This page was built for publication: Constructive generation of very hard 3-colorability instances
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2467358)
