On the Chromatic Number of Non-Sparse Random Intersection Graphs



Nikoletseas, Sotiris E, Raptopoulos, Christoforos L and Spirakis, Paul G ORCID: 0000-0001-5396-3749
(2017) On the Chromatic Number of Non-Sparse Random Intersection Graphs. THEORY OF COMPUTING SYSTEMS, 60 (1). pp. 112-127.

[img] Text
RIGs.pdf - Author Accepted Manuscript

Download (212kB)

Abstract

An intersection graph of n vertices assumes that each vertex is equipped with a subset of a global label set. Two vertices share an edge when their label sets intersect. Random intersection graphs (RIGs) (as defined in Karoński et al. Comb. Probab. Comput. J. 8, 131–159 (1999); Singer-Cohen (1995)) consider label sets formed by the following experiment: each vertex, independently and uniformly, examines all the labels (m in total) one by one. Each examination is independent and the vertex succeeds to put the label in her set with probability p. Such graphs can capture interactions in networks due to sharing of resources among nodes. In this paper, we discuss various structural and algorithmic results concerning random intersection graphs and we focus on the computational problem of properly coloring random instances of the binomial random intersection graphs model. For the latter, we consider a range of parameters m, p for which RIGs differ substantially from Erdős-Rényi random graphs and for which greedy approaches fail.

Item Type: Article
Uncontrolled Keywords: Random intersection graphs, Proper coloring, Martingales, Probabilistic method
Depositing User: Symplectic Admin
Date Deposited: 09 Feb 2017 17:01
Last Modified: 19 Jan 2023 07:19
DOI: 10.1007/s00224-016-9733-x
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3005508