Almost all graphs with 1.44n edges are 3-colorable
From MaRDI portal
Publication:3201078
DOI10.1002/rsa.3240020103zbMath0715.05026OpenAlexW2077154649MaRDI QIDQ3201078
No author found.
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
Related Items
Bins and balls: Large deviations of the empirical occupancy process, Sandwiching a densest subgraph by consecutive cores, On the Thickness of Sparse Random Graphs, Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability, Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability, The mixing time of the giant component of a random graph, On a greedy 2-matching algorithm and Hamilton cycles in random graphs with minimum degree at least three, Unnamed Item, A scaling limit for the length of the longest cycle in a sparse random digraph, Loose Hamilton Cycles in Regular Hypergraphs, Orientability Thresholds for Random Hypergraphs, Birth of a giant \((k_{1},k_{2})\)-core in the random digraph, On the satisfiability threshold and clustering of solutions of random 3-SAT formulas, A scaling limit for the length of the longest cycle in a sparse random graph, The Stripping Process Can be Slow: Part II, Almost all graphs with average degree 4 are 3-colorable, A critical point for random graphs with a given degree sequence, On the robustness of random \(k\)-cores, Hamilton cycles in random graphs with minimum degree at least 3: An improved analysis, Speed and concentration of the covering time for structured coupon collectors, Cores of random graphs are born Hamiltonian
Cites Work
