Almost all graphs with 1.44n edges are 3-colorable

DOI10.1002/RSA.3240020103zbMATH Open0715.05026OpenAlexW2077154649MaRDI QIDQ3201078FDOQ3201078

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

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

zbMATH Keywords

uniform asymptotic approximation3-colorable

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Many hard examples for resolution
• Coupon Collecting for Uneqal Probabilities
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• On circuits and subgraphs of chromatic graphs
• An Asymptotic Formula for the Differences of the Powers at Zero
• Title not available (Why is that?)

Cited In (22)

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

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)