Constructive generation of very hard 3-colorability instances

DOI10.1016/J.DAM.2006.07.015MaRDI QIDQ2467358zbMATH OpenOpenAlexFDO

Authors Kazunori Mizuno, Seiichi Nishihara

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

zbMATH Keywords

heuristicsphase transitionconstraint satisfactiongraph coloringsearchNP-completehard problem

Mathematics Subject Classification ID

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)

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
• Publication:4487450
• 3-colorability of pseudo-triangulations
• Hardness results for three kinds of colored connections of graphs

Cites work

• scientific article; zbMATH DE number 4002120 (Why is no real title available?)
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 67483 (Why is no real title available?)
• scientific article; zbMATH DE number 1149446 (Why is no real title available?)
• scientific article; zbMATH DE number 2243370 (Why is no real title available?)
• Consistency in networks of relations
• Exploiting the deep structure of constraint problems
• Frozen development in graph coloring
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
• Local optima topology for the \(k\)-coloring problem
• New methods to color the vertices of a graph
• On the Hardness of 4-Coloring a 3-Colorable Graph
• The hardest constraint problems: A double phase transition

Cited in

(9)

• Proper colorability of segment intersection graphs
• Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
• Expected polynomial-time randomized algorithm for graph coloring problem
• Low degree Nullstellensatz certificates for 3-colorability
• Using Hajós’ Construction to Generate Hard Graph 3-Colorability Instances
• Regular pattern-free coloring
• An incremental search heuristic for coloring vertices of a graph
• Proper colorability of segment intersection graphs
• Graphs with large girth and chromatic number are hard for Nullstellensatz

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)