Almost all graphs with 1.44n edges are 3-colorable

DOI10.1002/RSA.3240020103MaRDI QIDQ3201078zbMATH OpenOpenAlexFDO

Authors

Publication date 1991

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.3240020103

zbMATH Keywords

uniform asymptotic approximation3-colorable

Mathematics Subject Classification ID

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

Recommendations

• Almost all graphs with 2. 522\(n\) edges are not 3-colorable
• Almost all graphs with average degree 4 are 3-colorable
• On the chromatic number of random graphs
• scientific article; zbMATH DE number 1380613
• Almost all k-colorable graphs are easy to color

Cites work

• scientific article; zbMATH DE number 3127542 (Why is no real title available?)
• scientific article; zbMATH DE number 3069520 (Why is no real title available?)
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• An Asymptotic Formula for the Differences of the Powers at Zero
• Coupon Collecting for Uneqal Probabilities
• Many hard examples for resolution
• On circuits and subgraphs of chromatic graphs

Cited in

(22)

• On a greedy 2-matching algorithm and Hamilton cycles in random graphs with minimum degree at least three
• Cores of random graphs are born Hamiltonian
• Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
• A scaling limit for the length of the longest cycle in a sparse random graph
• Orientability Thresholds for Random Hypergraphs
• A critical point for random graphs with a given degree sequence
• On the satisfiability threshold and clustering of solutions of random 3-SAT formulas
• Hamilton cycles in random graphs with minimum degree at least 3: an improved analysis
• On the Thickness of Sparse Random Graphs
• The stripping process can be slow. II
• On the robustness of random \(k\)-cores
• Loose Hamilton Cycles in Regular Hypergraphs
• Almost all k-colorable graphs are easy to color
• Speed and concentration of the covering time for structured coupon collectors
• Almost all graphs with average degree 4 are 3-colorable
• Bins and balls: Large deviations of the empirical occupancy process
• Birth of a giant \((k_{1},k_{2})\)-core in the random digraph
• scientific article; zbMATH DE number 1380613 (Why is no real title available?)
• Sandwiching a densest subgraph by consecutive cores
• The mixing time of the giant component of a random graph
• A scaling limit for the length of the longest cycle in a sparse random digraph
• Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability

This page was built for publication: Almost all graphs with 1.44n edges are 3-colorable

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