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.
@article{bwmeta1.element.doi-10_7151_dmgt_1955,
author = {Katarzyna Rybarczyk},
title = {The Chromatic Number of Random Intersection Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {37},
year = {2017},
pages = {465-476},
zbl = {06705140},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1955}
}
Katarzyna Rybarczyk. The Chromatic Number of Random Intersection Graphs. Discussiones Mathematicae Graph Theory, Tome 37 (2017) pp. 465-476. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1955/