{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:44:07Z","timestamp":1787323447238,"version":"build-2736575974"},"reference-count":17,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>We study the evolution of the chromatic number of a random intersection graph and show that, in a certain range of parameters, these random graphs can be colored optimally with high probability using different greedy algorithms. Experiments on real network data confirm the positive theoretical predictions and suggest that heuristics for the clique and the chromatic number can work hand in hand proving mutual optimality.<\/jats:p>","DOI":"10.1137\/050647153","type":"journal-article","created":{"date-parts":[[2009,1,7]],"date-time":"2009-01-07T18:06:02Z","timestamp":1231351562000},"page":"288-299","source":"Crossref","is-referenced-by-count":13,"title":["Coloring Random Intersection Graphs and Complex Networks"],"prefix":"10.1137","volume":"23","author":[{"given":"Michael","family":"Behrisch","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anusch","family":"Taraz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Ueckerdt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2009,1,7]]},"reference":[{"key":"R1","unstructured":"R. Albert, H. Jeong, and A.L. Barab\u00e1si,\n                      Database of Self-Organized Networks\n                      , http:\/\/ www.nd.edu\/networks\/database\/index.html."},{"key":"R2","doi-asserted-by":"crossref","first-page":"12","DOI":"10.37236\/935","volume":"14","author":"Behrisch M.","year":"2007","journal-title":"Electron J. Combin.","ISSN":"https:\/\/id.crossref.org\/issn\/1077-8926","issn-type":"print"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.12.005"},{"key":"R4","unstructured":"R. Diestel,\n                      Graph Theory\n                      , Springer-Verlag, New York, 1997."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(200003)16:2<156::AID-RSA3>3.0.CO;2-H"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btg343"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"E. Godehardt and J. Jaworski,\n                      Two models of random intersection graphs and their applications\n                      , Electron. Notes Discrete Math. 10, Elsevier, Amsterdam, 2001.","DOI":"10.1016\/S1571-0653(04)00377-4"},{"key":"R8","unstructured":"R. Govindan and H. Tangmunarunkit,\n                      SCAN+Lucent Internet Map From the ISI\n                      , http:\/\/ www.isi.edu\/div7\/scan\/mercator\/maps.html, 1999."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.03.007"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"S. Janson, T. \u0141uczak, and A. Ruci\u0144ski,\n                      Random Graphs\n                      , John Wiley & Sons, New York, 2000.","DOI":"10.1002\/9781118032718"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548398003459"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.64.026118"},{"key":"R13","unstructured":"K. B. Singer,\n                      Random Intersection Graphs\n                      , Ph.D. thesis, Johns Hopkins University, Baltimore, MD, 1995."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20005"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0213035"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1021\/ci049920h"},{"key":"R17","unstructured":"M. Ueckerdt,\n                      F\u00e4rben von zuf\u00e4lligen Schnittgraphen\n                      , Diploma thesis, Humboldt-Universit\u00e4t zu Berlin, Berlin, Germany, 2005."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/050647153","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:02:47Z","timestamp":1787320967000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/050647153"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":17,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1137\/050647153"],"URL":"https:\/\/doi.org\/10.1137\/050647153","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]}}}