Almost all graphs with average degree 4 are 3-colorable
type: Item
instance of: scholarly article
title: Almost all graphs with average degree 4 are 3-colorable
zbMATH Open document ID: 1072.68076
DOI: 10.1016/S0022-0000(03)00120-X
author: D. Achlioptas
author: Cristopher Moore
published in: Journal of Computer and System Sciences
publication date: 2004-11-18T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 2116464
zbMATH Keywords: Random graphs
zbMATH Keywords: Regular random graphs
zbMATH Keywords: Graph coloring
zbMATH Keywords: Threshold phenomena
MaRDI profile type: Publication
cites work: Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
cites work: Q4705349
cites work: The asymptotic number of labeled graphs with given degree sequences
cites work: Q3682518
cites work: New methods to color the vertices of a graph
cites work: Almost all graphs with 1.44n edges are 3-colorable
cites work: Q3286850
cites work: A note on the non-colorability threshold of a random graph
cites work: Stable husbands
cites work: Solutions of ordinary differential equations as limits of pure jump markov processes
cites work: Q3917278
cites work: Q4526978
cites work: Size and connectivity of the \(k\)-core of a random graph
cites work: Analyses of load stealing models based on families of differential equations
cites work: Studying Balanced Allocations with Differential Equations
cites work: Q5624492
cites work: A critical point for random graphs with a given degree sequence
cites work: Coloring random graphs
cites work: Sudden emergence of a giant \(k\)-core in a random graph
cites work: Differential equations for random processes and random graphs
full work available at URL: s0022-0000(03)00120-x
OpenAlex ID: W4213277474
description: scientific article; zbMATH DE number 2116464