The Chromatic Number of Random Intersection Graphs

Katarzyna Rybarczyk. "The Chromatic Number of Random Intersection Graphs." Discussiones Mathematicae Graph Theory 37.2 (2017): 465-476. <http://eudml.org/doc/288015>.

@article{KatarzynaRybarczyk2017,
abstract = {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.},
author = {Katarzyna Rybarczyk},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {random intersection graphs; chromatic number; colouring algorithms},
language = {eng},
number = {2},
pages = {465-476},
title = {The Chromatic Number of Random Intersection Graphs},
url = {http://eudml.org/doc/288015},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Katarzyna Rybarczyk
TI - The Chromatic Number of Random Intersection Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 2
SP - 465
EP - 476
AB - 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.
LA - eng
KW - random intersection graphs; chromatic number; colouring algorithms
UR - http://eudml.org/doc/288015
ER -