The resolution complexity of random graph k-colorability

DOI10.1016/J.DAM.2005.05.004MaRDI QIDQ2581545zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

chromatic numbergraph coloringproof complexityrandom graphsresolution proofs

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(7)

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

Describes a project that uses

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)