{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T10:09:09Z","timestamp":1648894149874},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,12,9]],"date-time":"2016-12-09T00:00:00Z","timestamp":1481241600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,1]]},"DOI":"10.1007\/s00224-016-9733-x","type":"journal-article","created":{"date-parts":[[2016,12,9]],"date-time":"2016-12-09T05:55:06Z","timestamp":1481262906000},"page":"112-127","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Chromatic Number of Non-Sparse Random Intersection Graphs"],"prefix":"10.1007","volume":"60","author":[{"given":"Sotiris E.","family":"Nikoletseas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoforos L.","family":"Raptopoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,12,9]]},"reference":[{"key":"9733_CR1","doi-asserted-by":"crossref","unstructured":"Leone, P., Moraru, L., Powell, O., Rolim, J.D.P.: Localization algorithm for wireless ad-hoc sensor networks with traffic overhead minimization by emission inhibition. In: Proceedings of the 2nd International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS), pp 119\u2013129 (2006)","DOI":"10.1007\/11963271_11"},{"key":"9733_CR2","doi-asserted-by":"crossref","unstructured":"Caragiannis, I., Kaklamanis, C., Kranakis, E., Krizanc, D., Wiese, A.: Communication in wireless networks with directional antennas. In: Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp 344\u2013351 (2008)","DOI":"10.1145\/1378533.1378592"},{"issue":"1","key":"9733_CR3","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/s00446-007-0053-x","volume":"21","author":"C Busch","year":"2008","unstructured":"Busch, C., Magdon-Ismail, M., Sivrikaya, F., Yener, B.: Contention-free MAC protocols for asynchronous wireless sensor networks. Distrib. Comput. 21(1), 23\u201342 (2008)","journal-title":"Distrib. Comput."},{"key":"9733_CR4","doi-asserted-by":"publisher","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete problems. In: Proceedings of the 6th Annual ACM Symposium on Theory of Computing, pp. 47\u201363 (1974). doi: 10.1145\/800119.803884","DOI":"10.1145\/800119.803884"},{"key":"9733_CR5","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0020-0190(93)90246-6","volume":"45","author":"MM Halld\u00f3rsson","year":"1993","unstructured":"Halld\u00f3rsson, M.M.: A still better performance guarantee for approximate graph coloring. Inf. Process. Lett. 45, 19\u201323 (1993). doi: 10.1016\/0020-0190(93)90246-6","journal-title":"Inf. Process. Lett."},{"key":"9733_CR6","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3, 103\u2013128 (2007). doi: 10.4086\/toc.2007.v003a006","journal-title":"Theory Comput."},{"issue":"1","key":"9733_CR7","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/BF02122551","volume":"8","author":"B Bollob\u00e1s","year":"1988","unstructured":"Bollob\u00e1s, B.: The chromatic number of random graphs. Combinatorica 8(1), 49\u201355 (1988)","journal-title":"Combinatorica"},{"issue":"1","key":"9733_CR8","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/BF01375472","volume":"11","author":"T \u0141uczak","year":"2005","unstructured":"\u0141uczak, T.: The chromatic number of random graphs. Combinatorica 11(1), 45\u201354 (2005)","journal-title":"Combinatorica"},{"key":"9733_CR9","doi-asserted-by":"crossref","unstructured":"Dolev, S., Gilbert, S., Guerraoui, R., Newport, C.C.: Secure communication over radio channels. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pp 105\u2013114 (2008)","DOI":"10.1145\/1400751.1400767"},{"key":"9733_CR10","doi-asserted-by":"crossref","unstructured":"Dolev, S., Lahiani, L., Yung, M.: Secret swarm unitreactive k-secret sharing. In: Proceedings of the 8th International Conference on Cryptology in India (INDOCRYPT), pp 123\u2013137 (2007)","DOI":"10.1007\/978-3-540-77026-8_10"},{"key":"9733_CR11","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1017\/S0963548398003459","volume":"8","author":"M Karo\u0144ski","year":"1999","unstructured":"Karo\u0144ski, M., Sheinerman, E.R., Singer-Cohen, K.B.: On random intersection graphs: The subgraph problem. Comb. Probab. Comput. J. 8, 131\u2013159 (1999)","journal-title":"Comb. Probab. Comput. J."},{"key":"9733_CR12","unstructured":"Singer-Cohen, K.B.: Random Intersection Graphs. PhD thesis, John Hopkins University (1995)"},{"key":"9733_CR13","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/j.tcs.2008.06.047","volume":"406","author":"S Nikoletseas","year":"2008","unstructured":"Nikoletseas, S., Raptopoulos, C., Spirakis, P.G.: Large independent sets in general random intersection graphs. Theor. Comput. Sci. 406, 215\u2013224 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"9733_CR14","first-page":"67","volume-title":"Studies in Classification, Data Analysis and Knowledge Organization","author":"E Godehardt","year":"2002","unstructured":"Godehardt, E., Jaworski, J.: Two models of random intersection graphs for classification. In: Opitz, O., Schwaiger, M. (eds.) Studies in Classification, Data Analysis and Knowledge Organization, pp 67\u201382. Springer Verlag, Berlin, Heidelberg, New York (2002)"},{"issue":"2","key":"9733_CR15","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1002\/(SICI)1098-2418(200003)16:2<156::AID-RSA3>3.0.CO;2-H","volume":"16","author":"JA Fill","year":"2000","unstructured":"Fill, J.A., Sheinerman, E.R., Singer-Cohen, K.B.: Random intersection graphs when m = \u03c9(n): an equivalence theorem relating the evolution of the G(n, m, p) and G(n, p) models. Random Struct. Algoritm. 16(2), 156\u2013176 (2000)","journal-title":"Random Struct. Algoritm."},{"issue":"1\u20132","key":"9733_CR16","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1002\/rsa.20356","volume":"38","author":"K Rybarczyk","year":"2011","unstructured":"Rybarczyk, K.: Equivalence of a random intersection graph and G(n, p). Random Struct. Algoritm. 38(1\u20132), 205\u2013234 (2011)","journal-title":"Random Struct. Algoritm."},{"issue":"3","key":"9733_CR17","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1002\/rsa.20005","volume":"24","author":"D Stark","year":"2004","unstructured":"Stark, D.: The vertex degree distribution of random intersection graphs. Random Struct. Algoritm. 24(3), 249\u2013258 (2004)","journal-title":"Random Struct. Algoritm."},{"key":"9733_CR18","doi-asserted-by":"publisher","first-page":"Article ID 8727","DOI":"10.1155\/2011\/872703","volume":"2011","author":"Y Shang","year":"2011","unstructured":"Shang, Y.: On the isolated vertices and connectivity in random intersection graphs. Int. J. Comb. 2011, Article ID 872703 (2011). doi: 10.1155\/2011\/872703","journal-title":"Int. J. Comb."},{"key":"9733_CR19","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1137\/050647153","volume":"23","author":"M Behrisch","year":"2008","unstructured":"Behrisch, M., Taraz, A., Ueckerdt, M.: Coloring random intersection graphs and complex networks. SIAM J. Discrete Math. 23, 288\u2013299 (2008)","journal-title":"SIAM J. Discrete Math."},{"key":"9733_CR20","doi-asserted-by":"crossref","unstructured":"Nikoletseas, S., Raptopoulos, C., Spirakis, P.: Colouring non-sparse random intersection graphs. In: Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science (MFCS), pp 600\u2013611 (2009)","DOI":"10.1007\/978-3-642-03816-7_51"},{"key":"9733_CR21","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0012-365X(90)90149-C","volume":"81","author":"A Frieze","year":"1990","unstructured":"Frieze, A.: On the independence number of random graphs. Disc. Math. 81, 171\u2013175 (1990)","journal-title":"Disc. Math."},{"key":"9733_CR22","unstructured":"Ross, S.M.: Stochastic Processes, 2nd edn. Wiley (2000)"},{"key":"9733_CR23","doi-asserted-by":"crossref","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method. Wiley (2000)","DOI":"10.1002\/0471722154"},{"key":"9733_CR24","unstructured":"Nikoletseas, S., Raptopoulos, C., Spirakis, P.: On the independence number and hamiltonicity of uniform random intersection graphs. In: Proceedings of the 23rd IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp 1\u201311 (2009)"},{"key":"9733_CR25","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1016\/0097-3165(73)90005-8","volume":"14","author":"P Erdo\u030bs","year":"1973","unstructured":"Erdo\u030bs, P., Selfridge, J.: On a combinatorial game. J. Combinatorial Th. (A) 14, 298\u2013301 (1973)","journal-title":"J. Combinatorial Th. (A)"},{"key":"9733_CR26","doi-asserted-by":"crossref","unstructured":"Molloy, M., Reed, B.: Graph Colouring and the Probabilistic Method. Springer (2002)","DOI":"10.1007\/978-3-642-04016-0"},{"key":"9733_CR27","doi-asserted-by":"crossref","unstructured":"Bloznelis, M., Godehardt, E., Jaworski, J., Kurauskas, V., Rybarczyk, K.: Recent progress in complex network analysis - models of random intersection graphs. In: Lausen, B., Krolak-Schwerdt, S., Bhmer, M. (eds.) Data Science, Learning by Latent Structures, and Knowledge Discovery, pp 59\u201368. Springer (2015)","DOI":"10.1007\/978-3-662-44983-7_6"},{"key":"9733_CR28","doi-asserted-by":"crossref","unstructured":"Raptopoulos, C., Spirakis, P.: Simple and efficient greedy algorithms for hamilton cycles in random intersection graphs (2005)","DOI":"10.1007\/11602613_50"},{"issue":"40\u201342","key":"9733_CR29","doi-asserted-by":"crossref","first-page":"3714","DOI":"10.1016\/j.tcs.2010.06.022","volume":"411","author":"C Efthymiou","year":"2010","unstructured":"Efthymiou, C., Spirakis, P.G.: Sharp thresholds for Hamiltonicity in random intersection graphs. Theor. Comput. Sci. 411(40\u201342), 3714\u20133730 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"9733_CR30","doi-asserted-by":"crossref","unstructured":"Nikoletseas, S., Raptopoulos, C., Spirakis, P.G.: Maximum cliques in graphs with small intersection number and random intersection graphs. In: Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS), pp 728\u2013739 (2012)","DOI":"10.1007\/978-3-642-32589-2_63"},{"issue":"50","key":"9733_CR31","doi-asserted-by":"crossref","first-page":"5261","DOI":"10.1016\/j.tcs.2009.08.028","volume":"410","author":"S Nikoletseas","year":"2009","unstructured":"Nikoletseas, S., Raptopoulos, C., Spirakis, P.G.: Expander properties and the cover time of random intersection graphs. Theor. Comput. Sci. 410(50), 5261\u20135272 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9733_CR32","doi-asserted-by":"crossref","unstructured":"Cooper, C., Frieze, A.: The cover time of sparse random graphs. In: Random Structures and Algorithms, vol. 30, pp 1\u201316. Wiley (2007)","DOI":"10.1002\/rsa.20151"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9733-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-016-9733-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9733-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,16]],"date-time":"2019-09-16T10:35:29Z","timestamp":1568630129000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-016-9733-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,9]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["9733"],"URL":"https:\/\/doi.org\/10.1007\/s00224-016-9733-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,9]]}}}