Coloring random graphs in polynomial expected time

Martin Furer, C. R. Subramanian, C. E.Veni Madhavan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations


We consider the problem of vertex coloring random k-colorable graphs using k colors. We consider two different models for generating random graphs. We give algorithms for coloring random graphs in these models, with running times polynomial on the average. The first model is discussed in Turner [6] and the second model is discussed in Dyer and Frieze [3]. Our results improve the these current results for this problem by removing the assumption ofconstant edge probability used in these models.

Original languageEnglish (US)
Title of host publicationAlgorithms and Computation - 4th International Symposium, ISAAC 1993, Proceedings
EditorsKam Wing Ng, Prabhakar Raghavan, N.V. Balasubramanian, Francis Y.L. Chin
PublisherSpringer Verlag
Number of pages7
ISBN (Print)9783540575689
StatePublished - 1993
Event4th International Symposium on Algorithms and Computation, ISAAC 1993 - Hong Kong, China
Duration: Dec 15 1993Dec 17 1993

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume762 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other4th International Symposium on Algorithms and Computation, ISAAC 1993
CityHong Kong

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Coloring random graphs in polynomial expected time'. Together they form a unique fingerprint.

Cite this