{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T04:45:32Z","timestamp":1764132332664},"reference-count":57,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1984,10,1]],"date-time":"1984-10-01T00:00:00Z","timestamp":465436800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[1984,10]]},"DOI":"10.1007\/bf01874388","type":"journal-article","created":{"date-parts":[[2005,7,2]],"date-time":"2005-07-02T18:31:47Z","timestamp":1120329107000},"page":"183-200","source":"Crossref","is-referenced-by-count":32,"title":["Colouring random graphs"],"prefix":"10.1007","volume":"1","author":[{"given":"Colin","family":"McDiarmid","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01874388_CR1","unstructured":"E.A. Bender and H.S. Wilf, A theoretical analysis of backtracking in the graph coloring problem (1983) preprint."},{"key":"BF01874388_CR2","volume-title":"Graph Theory, Graduate Texts in Mathematics 63","author":"B. Bollob\u00e1s","year":"1979","unstructured":"B. Bollob\u00e1s, Graph Theory, Graduate Texts in Mathematics 63 (Springer Verlag, Berlin, 1979)."},{"key":"BF01874388_CR3","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1017\/S0305004100053056","volume":"80","author":"B. Bollob\u00e1s","year":"1976","unstructured":"B. Bollob\u00e1s and P. Erd\u0151s, Cliques in random graphs, Math. Proc. Camb. Phil. Soc. 80 (1976) 419.","journal-title":"Math. Proc. Camb. Phil. Soc."},{"key":"BF01874388_CR4","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1145\/359094.359101","volume":"22","author":"D. Br\u00e9laz","year":"1979","unstructured":"D. Br\u00e9laz, New methods to color the vertices of a graph, Comm. A.C.M. 22 (1979) 251.","journal-title":"Comm. A.C.M."},{"key":"BF01874388_CR5","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1287\/mnsc.19.4.456","volume":"19","author":"J.R. Brown","year":"1972","unstructured":"J.R. Brown, Chromatic scheduling and the chromatic number problem, Man. Sci. 19 (1972) 456.","journal-title":"Man. Sci."},{"key":"BF01874388_CR6","first-page":"497","volume":"14","author":"Y.D. Burtin","year":"1973","unstructured":"Y.D. Burtin, Aymptotic estimates of the diameter, independence and dominance numbers of a random graph, Sov. Math. Dokl. 14 (1973) 497.","journal-title":"Sov. Math. Dokl."},{"key":"BF01874388_CR7","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1093\/comjnl\/14.1.38","volume":"14","author":"N. Christofides","year":"1971","unstructured":"N. Christofides, An algorithm for the chromatic number of a graph, Comput. J. 14 (1971) 38.","journal-title":"Comput. J."},{"key":"BF01874388_CR8","unstructured":"N. Christofides, Graph Theory \u2014 an Algorithmic Approach (Academic Press, 1975)."},{"key":"BF01874388_CR9","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1137\/0206046","volume":"6","author":"V. Chv\u00e1tal","year":"1977","unstructured":"V. Chv\u00e1tal, Determining the stability number of a graph, SIAM J. Comput. 6 (1977) 643.","journal-title":"SIAM J. Comput."},{"key":"BF01874388_CR10","doi-asserted-by":"crossref","first-page":"1402","DOI":"10.1287\/opre.28.6.1402","volume":"28","author":"V. Chv\u00e1tal","year":"1980","unstructured":"V. Chv\u00e1tal, Hard knapsack problems, Oper. Res. 28 (1980) 1402.","journal-title":"Oper. Res."},{"key":"BF01874388_CR11","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1137\/0202026","volume":"2","author":"D.G. Corneil","year":"1973","unstructured":"D.G. Corneil and B. Graham, An algorithm for determining the chromatic number of a graph, SIAM J. Comput. 2 (1973) 311.","journal-title":"SIAM J. Comput."},{"key":"BF01874388_CR12","series-title":"Proc. 5th British Comb. Conf.","first-page":"151","volume-title":"Sequential colourings of graphs","author":"F.D.J. Dunstan","year":"1976","unstructured":"F.D.J. Dunstan, Sequential colourings of graphs, Proc. 5th British Comb. Conf., ed. C. St. J.A. Nash-Williams and J. Sheehan (Utilitas Mathematica, Winnipeg, 1976) p. 151."},{"key":"BF01874388_CR13","unstructured":"K. D\u00fcrre, Approximate algorithms for coloring large graphs, Datenstrukt, Graphen, Algorithm 3 Fachtag Graphentheor. Konz. Inf., Linz 1977, (1978) p. 191."},{"key":"BF01874388_CR14","doi-asserted-by":"crossref","first-page":"34","DOI":"10.4153\/CJM-1959-003-9","volume":"11","author":"P. Erd\u0151s","year":"1959","unstructured":"P. Erd\u0151s, Graph theory and probability, Can. J. Math. 11 (1959) 34.","journal-title":"Can. J. Math."},{"key":"BF01874388_CR15","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1112\/S0025579300003260","volume":"9","author":"P. Erd\u0151s","year":"1962","unstructured":"P. Erd\u0151s, On circuits and subgraphs of random graphs, Mathematika 9 (1962) 170.","journal-title":"Mathematika"},{"key":"BF01874388_CR16","first-page":"17","volume":"5","author":"P. Erd\u0151s","year":"1960","unstructured":"P. Erd\u0151s and A. R\u00e9nyi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960) 17.","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci."},{"key":"BF01874388_CR17","volume-title":"Probabilistic Methods in Combinatorics","author":"P. Erd\u0151s","year":"1974","unstructured":"P. Erd\u0151s and J. Spencer, Probabilistic Methods in Combinatorics (Academic Press, New York and London, 1974)."},{"key":"BF01874388_CR18","first-page":"43","volume":"23","author":"M.R. Garey","year":"1976","unstructured":"M.R. Garey and D.S. Johnson, The complexity of near optimal graph coloring, J.A.C.M. 23 (1976) 43.","journal-title":"J.A.C.M."},{"key":"BF01874388_CR19","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson, Computers and Intractability (Freeman, San Francisco, 1979)."},{"key":"BF01874388_CR20","unstructured":"G.R. Grimmett, Random graph theorems, Trans. 7th Prague Conf. on Information Th. and related topics A (1977) p. 203."},{"key":"BF01874388_CR21","first-page":"201","volume-title":"Selected Topics in Graph Theory 2","author":"G.R. Grimmett","year":"1983","unstructured":"G.R. Grimmett, Random graphs, in: Selected Topics in Graph Theory 2, ed. L. Beineke and R. Wilson (Academic Press, London, 1983) p. 201."},{"key":"BF01874388_CR22","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1017\/S0305004100051124","volume":"77","author":"G.R. Grimmett","year":"1975","unstructured":"G.R. Grimmett and C.J.H. McDiarmid, On colouring random graphs, Math. Proc. Camb. Phil. Soc. 77 (1975) 313.","journal-title":"Math. Proc. Camb. Phil. Soc."},{"key":"BF01874388_CR23","unstructured":"D. Hochbaum, Easy solutions for theK-center problem or the dominating set problem on random graphs (1982) preprint."},{"key":"BF01874388_CR24","series-title":"Proc. 5th S.E. Conf. on Combinatorics, Graph Theory and Computing","first-page":"513","volume-title":"Worst case behaviour of graph colouring algorithms","author":"D.S. Johnson","year":"1974","unstructured":"D.S. Johnson, Worst case behaviour of graph colouring algorithms, Proc. 5th S.E. Conf. on Combinatorics, Graph Theory and Computing (Utilitas Mathematica, Winnipeg, 1974) p. 513."},{"key":"BF01874388_CR25","series-title":"Technical Report 82-CSE-6","volume-title":"Probabilistic bounds and heuristic algorithms for coloring large random graphs","author":"A. Johri","year":"1982","unstructured":"A. Johri and D.W. Matula, Probabilistic bounds and heuristic algorithms for coloring large random graphs, Technical Report 82-CSE-6 (Southern Methodist University, Dallas, Texas, 1982)."},{"key":"BF01874388_CR26","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1002\/jgt.3190060402","volume":"6","author":"M. Karonski","year":"1982","unstructured":"M. Karonski, A review of random graphs, J. Graph. Th. 6 (1982) 349.","journal-title":"J. Graph. Th."},{"key":"BF01874388_CR27","first-page":"1","volume-title":"Algorithms and Complexity","author":"R.M. Karp","year":"1976","unstructured":"R.M. Karp, The probabilistic analysis of some combinatorial search algorithms, in: Algorithms and Complexity, ed. J.F. Traub (Academic Press, New York, 1976) p. 1."},{"key":"BF01874388_CR28","doi-asserted-by":"crossref","unstructured":"T. Kawaguchi, H. Nakano and Y. Nakanishi, Probabilistic analysis of a heuristic graph coloring algorithm (1982) preprint.","DOI":"10.1002\/ecja.4410650603"},{"key":"BF01874388_CR29","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1017\/S0305004100059181","volume":"91","author":"D.G. Kelly","year":"1982","unstructured":"D.G. Kelly and J.G. Oxley, Asymptotic properties of random subsets of projective spaces, Math. Proc. Camb. Phil. Soc. 91 (1982) 119.","journal-title":"Math. Proc. Camb. Phil. Soc."},{"key":"BF01874388_CR30","first-page":"14","volume":"104","author":"A.D. Korsunov","year":"1980","unstructured":"A.D. Korsunov, The chromatic number ofn-vertex graphs, Metody Diskret. Analiz. No. 35 (1980) 14\u201344, 104 (in Russian).","journal-title":"Metody Diskret. Analiz. No. 35"},{"key":"BF01874388_CR31","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1007\/3-540-08442-8_114","volume":"56","author":"L. Ku\u0107era","year":"1977","unstructured":"L. Ku\u0107era, Expected behaviour of graph coloring algorithms, Lecture Notes in Computer Science 56 (1977) p. 447.","journal-title":"Lecture Notes in Computer Science"},{"key":"BF01874388_CR32","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/0020-0190(76)90065-X","volume":"5","author":"E.L. Lawler","year":"1976","unstructured":"E.L. Lawler, A note on the complexity of the chromatic number problem, Inf. Proc. Lett. 5 (1976) 66.","journal-title":"Inf. Proc. Lett."},{"key":"BF01874388_CR33","doi-asserted-by":"crossref","first-page":"489","DOI":"10.6028\/jres.084.024","volume":"84","author":"F.T. Leighton","year":"1979","unstructured":"F.T. Leighton, A graph coloring algorithm for large scheduling problems, J. Res. Nat. Bur. Stand. 84 (1979) 489.","journal-title":"J. Res. Nat. Bur. Stand."},{"key":"BF01874388_CR34","unstructured":"D.W. Matula, On the complete subgraphs of a random graph, Comb. Math. and its Appls. (Chapel Hill, N.C., 1970) p. 356."},{"key":"BF01874388_CR35","first-page":"A","volume":"19","author":"D.W. Matula","year":"1972","unstructured":"D.W. Matula, The employee party problem, Not. A.M.S. 19 (1972) A-382.","journal-title":"Not. A.M.S."},{"key":"BF01874388_CR36","unstructured":"D.W. Matula, private communication (1982)."},{"key":"BF01874388_CR37","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/B978-1-4832-3187-7.50015-5","volume-title":"Graph Theory and Computing","author":"D.W. Matula","year":"1972","unstructured":"D.W. Matula, G. Marble and J.D. Isaacson, Graph colouring algorithms, in: Graph Theory and Computing, ed. R.C. Read (Academic Press, New York, 1972) p. 109."},{"key":"BF01874388_CR38","unstructured":"C.J.H. McDiarmid, Determining the chromatic number of a graph, Technical Report STAN-CS-76-576 (Stanford University, 1976)."},{"key":"BF01874388_CR39","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0208001","volume":"8","author":"C.J.H. McDiarmid","year":"1979","unstructured":"C.J.H. McDiarmid, Determining the chromatic number of a graph, SIAM J. Comput. 8 (1979) 1.","journal-title":"SIAM J. Comput."},{"key":"BF01874388_CR40","series-title":"Pitman Research Notes in Mathematics","first-page":"76","volume-title":"Graph Theory and Combinatorics","author":"C.J.H. McDiarmid","year":"1979","unstructured":"C.J.H. McDiarmid, Colouring random graphs badly, in: Graph Theory and Combinatorics, ed. R.J. Wilson (Pitman Research Notes in Mathematics 34, Pitman, London, 1979) p. 76."},{"key":"BF01874388_CR41","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1017\/S0305004100059648","volume":"92","author":"C.J.H. McDiarmid","year":"1982","unstructured":"C.J.H. McDiarmid, Achromatic numbers of random graphs, Math. Proc. Camb. Phil. Soc. 92 (1982) 21.","journal-title":"Math. Proc. Camb. Phil. Soc."},{"key":"BF01874388_CR42","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/0166-218X(83)90022-7","volume":"5","author":"C.J.H. McDiarmid","year":"1983","unstructured":"C.J.H. McDiarmid, On the chromatic forcing number of a random graph, Discr. Appl. Math. 5 (1983) 123.","journal-title":"Discr. Appl. Math."},{"key":"BF01874388_CR43","unstructured":"D.M. Miller, An algorithm for determining the chromatic number of a graph, Proc. 5th Manitoba Conf. on Numerical Math., ed. Hartnell and Williams (1975) p. 533."},{"key":"BF01874388_CR44","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1093\/comjnl\/19.2.182","volume":"19","author":"J. Mitchem","year":"1976","unstructured":"J. Mitchem, On various algorithms for estimating the chromatic number of a graph, Comput. J. 19 (1976) 182.","journal-title":"Comput. J."},{"key":"BF01874388_CR45","unstructured":"A. Punter, private communications."},{"key":"BF01874388_CR46","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1093\/comjnl\/23.4.307","volume":"23","author":"G. Schmidt","year":"1980","unstructured":"G. Schmidt and T. Str\u00f6hleim, Timertable construction \u2014 an annotated bibliography, Comput. J. 23 (1980) 307.","journal-title":"Comput. J."},{"key":"BF01874388_CR47","unstructured":"J. Schmidt-Pruzan, Probabilistic analysis of strong hypergraph coloring algorithms and the strong chromatic number (1983) preprint."},{"key":"BF01874388_CR48","unstructured":"J. Schmidt-Pruzan, E. Shamir and E. Upfal, Random hypergraph coloring algorithms and the weak chromatic number (1983) preprint."},{"key":"BF01874388_CR49","unstructured":"E. Shamir and E. Upfal, Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces (1982) preprint."},{"key":"BF01874388_CR50","series-title":"Applied Computer Science","volume-title":"Zufallsgraphen","author":"G. Tinhofer","year":"1980","unstructured":"G. Tinhofer, Zufallsgraphen (Applied Computer Science 17, Hanser, Munich and Vienna, 1980)."},{"issue":"73","key":"BF01874388_CR51","first-page":"321","volume":"25","author":"I. Tomescu","year":"1981","unstructured":"I. Tomescu, On the chromatic number of almost all graphs, Bull. Math. de la Soc. Sci. Math. de la R.S. de Roumanie Tome 25(73), nr. 3 (1981) 321.","journal-title":"Bull. Math. de la Soc. Sci. Math. de la R.S. de Roumanie Tome"},{"key":"BF01874388_CR52","unstructured":"W.F. de la Vega, On the chromatic number of sparse random graphs (1983) preprint."},{"key":"BF01874388_CR53","unstructured":"W.F. de la Vega, Crowded graphs can be colored within 1+\u03b5 in polynomial time (1983) preprint."},{"key":"BF01874388_CR54","first-page":"385","volume":"21","author":"C.C. Wang","year":"1974","unstructured":"C.C. Wang, An algorithm for the chromatic number of a graph, J.A.C.M. 21 (1974) 385.","journal-title":"J.A.C.M."},{"key":"BF01874388_CR55","doi-asserted-by":"crossref","unstructured":"A. Wigderson, A new approximate graph coloring algorithm (1983) preprint.","DOI":"10.1145\/800070.802207"},{"key":"BF01874388_CR56","doi-asserted-by":"crossref","unstructured":"H.S. Wilf, Backtrack: an O(1) expected time algorithm for the graph coloring problem (1983) preprint.","DOI":"10.1016\/0020-0190(84)90013-9"},{"key":"BF01874388_CR57","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1017\/S0305004100060205","volume":"92","author":"B. Pittel","year":"1982","unstructured":"B. Pittel, On the probable behaviour of some algorithms for finding the stability number of a graph, Math. Proc. Camb. Phil. Soc. 92 (1982) 511.","journal-title":"Math. Proc. Camb. Phil. Soc."}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01874388.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01874388\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01874388","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T03:46:06Z","timestamp":1586317566000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01874388"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1984,10]]},"references-count":57,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1984,10]]}},"alternative-id":["BF01874388"],"URL":"https:\/\/doi.org\/10.1007\/bf01874388","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[1984,10]]}}}