The resolution complexity of random graph k-colorability

DOI10.1016/J.DAM.2005.05.004zbMATH Open1082.05080OpenAlexW2144512014MaRDI QIDQ2581545FDOQ2581545

Authors: Yanyan Li 

Publication date: 10 January 2006

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2005.05.004

Recommendations

• scientific article; zbMATH DE number 1775444
• An Upper Bound on the Space Complexity of Random Formulae in Resolution
• The resolution complexity of independent sets and vertex covers in random graphs
• Space complexity of random formulae in resolution
• Thresholds for colourability and satisfiability in random graphs and Boolean formulae

zbMATH Keywords

chromatic numbergraph coloringproof complexityrandom graphsresolution proofs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Frozen development in graph coloring
• Backtrack: An O(1) expected time algorithm for the graph coloring problem
• A machine program for theorem-proving
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Many hard examples for resolution
• Title not available (Why is that?)
• Title not available (Why is that?)
• The chromatic number of random graphs
• Short proofs are narrow—resolution made simple
• A note on the complexity of the chromatic number problem
• Title not available (Why is that?)
• Experimental results on the crossover point in random 3-SAT
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• Approximating the independence number and the chromatic number in expected polynomial time
• A theoretical analysis of backtracking in the graph coloring problem
• The dynamics of proving uncolourability of large random graphs: I. Symmetric colouring heuristic
• Principles and Practice of Constraint Programming – CP 2004
• The two possible values of the chromatic number of a random graph
• Almost all graphs with 2. 522\(n\) edges are not 3-colorable
• Genetic and hybrid algorithms for graph coloring
• The efficiency of resolution and Davis-Putnam procedures
• Title not available (Why is that?)
• The Lovász number of random graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Almost all graphs with average degree 4 are 3-colorable

Cited In (7)

• On the resolution complexity of graph non-isomorphism
• Limitations of restricted branching in clause learning
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Resolution complexity of perfect matching principles for sparse graphs
• On the CNF-complexity of bipartite graphs containing no squares
• The resolution complexity of independent sets and vertex covers in random graphs
• Thresholds for colourability and satisfiability in random graphs and Boolean formulae

Uses Software

• DIMACS

This page was built for publication: The resolution complexity of random graph \(k\)-colorability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2581545)