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

doi:10.1007/11561071_21

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

Computer Science

Research output: Contribution to journal › Conference article › peer-review

Abstract

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

Original language	English (US)
Pages (from-to)	215-225
Number of pages	11
Journal	Lecture Notes in Computer Science
Volume	3669
DOIs	https://doi.org/10.1007/11561071_21
State	Published - 2005
Event	13th Annual European Symposium on Algorithms, ESA 2005 - Palma de Mallorca, Spain Duration: Oct 3 2005 → Oct 6 2005

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/11561071_21

Cite this

@article{b0a50fe7dad045f3a6b424ccb036c720,

title = "5-regular graphs are 3-colorable with positive probability",

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

author = "J. D{\'i}az and G. Grammatikopoulos and Kaporis, {A. C.} and Kirousis, {L. M.} and X. P{\'e}rez and Sotiropoulos, {D. G.}",

year = "2005",

doi = "10.1007/11561071_21",

language = "English (US)",

volume = "3669",

pages = "215--225",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer Science and Business Media Deutschland GmbH",

note = "13th Annual European Symposium on Algorithms, ESA 2005 ; Conference date: 03-10-2005 Through 06-10-2005",

}

TY - JOUR

T1 - 5-regular graphs are 3-colorable with positive probability

AU - Díaz, J.

AU - Grammatikopoulos, G.

AU - Kaporis, A. C.

AU - Kirousis, L. M.

AU - Pérez, X.

AU - Sotiropoulos, D. G.

PY - 2005

Y1 - 2005

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

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

UR - http://www.scopus.com/inward/record.url?scp=27144473642&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=27144473642&partnerID=8YFLogxK

U2 - 10.1007/11561071_21

DO - 10.1007/11561071_21

M3 - Conference article

AN - SCOPUS:27144473642

SN - 0302-9743

VL - 3669

SP - 215

EP - 225

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - 13th Annual European Symposium on Algorithms, ESA 2005

Y2 - 3 October 2005 through 6 October 2005

ER -

5-regular graphs are 3-colorable with positive probability

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this