Refine
Keywords
- colouring (1)
- complex networks (1)
- intersection graphs (1)
- random graphs (1)
Project
- A5 (1)
Application Area
- A (1)
Random intersection graphs naturally exhibit a certain amount of transitivity and hence can
be used to model real--world networks. We study the evolution of the chromatic number
of a random intersection graph and show that, in a certain range of parameters,
these random graphs can be coloured optimally with high probability using different greedy
algorithms.
Experiments on real network data confirm the positive theoretical predictions and
suggest that heuristics for the clique and the chromatic number can work hand in hand
proving mutual optimality.