THE CHROMATIC NUMBER OF RANDOM INTERSECTION GRAPHS

被引：2

作者：

Rybarczyk, Katarzyna ^{[1
]}

机构：

[1] Adam Mickiewicz Univ, Fac Math & Comp Sci, PL-60769 Poznan, Poland

来源：

DISCUSSIONES MATHEMATICAE GRAPH THEORY | 2017年 / 37卷 / 02期

关键词：

random intersection graphs; chromatic number; colouring algorithms; COMPONENT EVOLUTION; EQUIVALENCE; G(N; P);

D O I：

10.7151/dmgt.1955

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We study problems related to the chromatic number of a random inter section 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 -> infinity. Moreover we find a range of parameters for which the chromatic number of G (n, m, p) asymptotically equals its clique number.

引用

页码：465 / 476

页数：12

共 18 条

[1]

Behrisch M, 2007, ELECTRON J COMB, V14

[2] COLORING RANDOM INTERSECTION GRAPHS AND COMPLEX NETWORKS [J].

Behrisch, Michael ;

Taraz, Anusch ;

Ueckerdt, Michael .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (01) :288-299

[3] COMPONENT EVOLUTION IN GENERAL RANDOM INTERSECTION GRAPHS [J].

Bloznelis, Mindaugas .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 24 (02) :639-654

[4] THE CHROMATIC NUMBER OF RANDOM GRAPHS [J].

BOLLOBAS, B .

COMBINATORICA, 1988, 8 (01) :49-55

[5]

BOLLOBAS B, 1976, MATH PROC CAMBRIDGE, V80, P419, DOI 10.1017/S0305004100053056

[6]

Fill JA, 2000, RANDOM STRUCT ALGOR, V16, P156, DOI 10.1002/(SICI)1098-2418(200003)16:2<156::AID-RSA3>3.0.CO

[7]

2-H

[8]

Frieze A, 1997, RANDOM STRUCT ALGOR, V10, P5, DOI 10.1002/(SICI)1098-2418(199701/03)10:1/2<5::AID-RSA2>3.0.CO

[9]

2-Z

[10] COLORING RANDOM GRAPHS [J].

GRIMMETT, GR ;

MCDIARMID, CJH .

MATHEMATICAL PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1975, 77 (MAR) :313-324

← 1 2 →