A note on the non-colorability threshold of a random graph

Alexis C. Kaporis, Lefteris M. Kirousis, Yannis C. Stamatiou

Research output: Contribution to journalArticlepeer-review


In this paper we consider the problem of establishing a value r0 such that almost all random graphs with n vertices and rn edges, r > r 0, are asymptotically not 3-colorable. In our approach we combine the concept of rigid legal colorings introduced by Achlioptas and Molloy with the occupancy problem for random allocations of balls into bins. Using the sharp estimates obtained by Kamath et al. of the probability that no bin is empty after the random placement of the balls and exploiting the relationship between the placement of balls and the rigid legal colorings, we improve the value r0 = 2.522 previously obtained by Achlioptas and Molloy to r 0 = 2.495.

Original languageEnglish (US)
Pages (from-to)1-12
Number of pages12
JournalElectronic Journal of Combinatorics
Issue number1 R
StatePublished - 2000

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'A note on the non-colorability threshold of a random graph'. Together they form a unique fingerprint.

Cite this