5-regular graphs are 3-colorable with positive probability

J. Díaz, G. Grammatikopoulos, A. C. Kaporis, L. M. Kirousis, X. Pérez, D. G. Sotiropoulos

Research output: Contribution to journalConference articlepeer-review


We show that uniformly random 5-regular graphs of n vertices are 3-colorable with probability that is positive independently of n.

Original languageEnglish (US)
Pages (from-to)215-225
Number of pages11
JournalLecture Notes in Computer Science
StatePublished - 2005
Event13th Annual European Symposium on Algorithms, ESA 2005 - Palma de Mallorca, Spain
Duration: Oct 3 2005Oct 6 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of '5-regular graphs are 3-colorable with positive probability'. Together they form a unique fingerprint.

Cite this