Geodesic
The Chromatic Number of Random Intersection Graphs
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 2, pp. 465-476

Voir la notice de l'article provenant de la source Library of Science

We study problems related to the chromatic number of a random intersection graph G(n,m, p). We introduce two new algorithms which colour G(n,m, p) with almost optimum number of colours with probability tending to 1 as n → ∞. Moreover we find a range of parameters for which the chromatic number of G(n,m, p) asymptotically equals its clique number.
Keywords: random intersection graphs, chromatic number, colouring algorithms 
Rybarczyk, Katarzyna. The Chromatic Number of Random Intersection Graphs. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 2, pp. 465-476. http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a10/
@article{DMGT_2017_37_2_a10,
     author = {Rybarczyk, Katarzyna},
     title = {The {Chromatic} {Number} of {Random} {Intersection} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {465--476},
     year = {2017},
     volume = {37},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a10/}
}
TY  - JOUR
AU  - Rybarczyk, Katarzyna
TI  - The Chromatic Number of Random Intersection Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 465
EP  - 476
VL  - 37
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a10/
LA  - en
ID  - DMGT_2017_37_2_a10
ER  - 
%0 Journal Article
%A Rybarczyk, Katarzyna
%T The Chromatic Number of Random Intersection Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 465-476
%V 37
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a10/
%G en
%F DMGT_2017_37_2_a10

[1] M. Behrisch, Component evolution in random intersection graphs, Electron. J. Com- bin. 14 (2007) R17.

[2] M. Behrisch, A. Taraz and M. Ueckerdt, Coloring random intersection graphs and complex networks, SIAM J. Discrete Math. 23 (2009) 288-299. doi: 10.1137/050647153

[3] M. Bloznelis, Component evolution in general random intersection graphs, SIAM J. Discrete Math. 24 (2010) 639-654. doi: 10.1137/080713756

[4] B. Bollobás, The chromatic number of random graphs, Combinatorica 8 (1988) 49-55. doi: 10.1007/BF02122551

[5] B. Bollobas and P. Erdős, Cliques in random graphs, Math. Proc. Cambridge Philos. Soc. 80 (1976) 419-427. doi: 10.1017/S0305004100053056

[6] J.A. Fill, E.R. Scheinerman and K.B. Singer-Cohen, Random intersection graphs when m = !(n): An equivalence theorem relating the evolution of the G(n,m, p) and G(n, p) models, Random Structures Algorithms 16 (2000) 156-176. doi: 10.1002/(SICI)1098-2418(200003)16:2h156::AID-RSA3i3.0.CO;2-H

[7] A. Frieze and C. McDiarmid, Algorithmic theory of random graphs, Random Struc- tures Algorithms 10 (1997) 5-42. doi: 10.1002/(SICI)1098-2418(199701/03)10:1/2h5::AID-RSA2i3.0.CO;2-Z

[8] G.R. Grimmett and C.J.H. McDiarmid, On colouring random graphs, Math. Proc. Cambridge Philos. Soc. 77 (1975) 313-324. doi: 10.1017/S0305004100051124

[9] S. Janson, T. Luczak and A. Ruciński, Random Graphs (Wiley, 2001).

[10] M. Karoński, E.R. Scheinerman and K.B. Singer-Cohen, On random intersection graphs: The subgraph problem, Combin. Probab. Comput. 8 (1999) 131-159. doi: 10.1017/S0963548398003459

[11] V. Kurauskas and K. Rybarczyk, On the chromatic index of random uniform hyper- graphs, SIAM J. Discrete Math. 29 (2015) 541-558. doi: 10.1137/130942292

[12] T. Luczak, The chromatic number of random graphs, Combinatorica 11 (1991) 45-54. doi: 10.1007/BF01375472

[13] S. Nikoletseas, C. Raptopoulos and P.G. Spirakis, Colouring non-sparse random intersection graphs, in: Mathematical Foundations of Computer Science 2009, Lec- ture Notes in Comput. Sci. 5734, R. Královiˇc, D. Niwiński (Ed(s)), (Springer Berlin Heidelberg, 2009) 600-611. doi: 10.1007/978-3-642-03816-7 51

[14] K. Rybarczyk, Equivalence of the random intersection graph and G(n, p), Random Structures Algorithms 38 (2011) 205-234. doi: 10.1002/rsa.20356

[15] K. Rybarczyk, Constructions of independent sets in random intersection graphs, Theoret. Comput. Sci. 524 (2014) 103-125. doi: 10.1016/j.tcs.2014.01.006

[16] E. Shamir and E. Upfal, Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces, J. Algorithms 5 (1984) 488-501. doi: 10.1016/0196-6774(84)90003-8