The Chromatic Number of Random Intersection Graphs

• Autorzy: Katarzyna Rybarczyk
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

random intersection graphs; chromatic number; colouring algorithms

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 2
• Strony: 465-476

Daty

wydano

2017-05-01

otrzymano

2015-11-16

poprawiono

2016-09-27

zaakceptowano

2016-09-27

online

2017-04-01

Twórcy

autor

Katarzyna Rybarczyk

• Adam Mickiewicz University Faculty of Mathematics and Computer Science 60–769 Poznań,

Identyfikatory

DOI

10.7151/dmgt.1955