Almost all graphs with 2. 522\(n\) edges are not 3-colorable

zbMath0919.05056MaRDI QIDQ1298442

V. Pereyra

Publication date: 22 August 1999

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/119877

Mathematics Subject Classification ID

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

Related Items (6)

An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm ⋮ Upper-bounding the \(k\)-colorability threshold by counting covers ⋮ Estimating satisfiability ⋮ When does the giant component bring unsatisfiability? ⋮ The resolution complexity of random graph \(k\)-colorability ⋮ A novel giant-subgraph phase-transition in sparse random \(k\)-partite graphs

This page was built for publication: Almost all graphs with 2. 522\(n\) edges are not 3-colorable