COLORING RANDOM GRAPHS

被引：197

作者：

GRIMMETT, GR ^{[1
]}

MCDIARMID, CJH ^{[1
]}

机构：

[1] MATH INST,OXFORD,ENGLAND

来源：

MATHEMATICAL PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY | 1975年 / 77卷 / MAR期

关键词：

D O I：

10.1017/S0305004100051124

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

引用

收藏

页码：313 / 324

页数：12

相关论文

共 50 条

[41] Coloring semi-random graphs in polynomial expected time
Subramanian, CR
Madhavan, CEV
FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE, 1994, 880 : 137 - 148
[42] An Experimental Analysis of Vertex Coloring Algorithms on Sparse Random Graphs
Healy, Patrick
Ju, Andrew
APPLIED ALGORITHMS, 2014, 8321 : 174 - 186
[43] A spectral technique for coloring random 3-colorable graphs
Alon, N
Kahale, N
SIAM JOURNAL ON COMPUTING, 1997, 26 (06) : 1733 - 1748
[44] Coloring Complete and Complete Bipartite Graphs from Random Lists
Carl Johan Casselgren
Roland Häggkvist
Graphs and Combinatorics, 2016, 32 : 533 - 542
[45] Coloring Complete and Complete Bipartite Graphs from Random Lists
Casselgren, Carl Johan
Haggkvist, Roland
GRAPHS AND COMBINATORICS, 2016, 32 (02) : 533 - 542
[46] Coloring graphs of various maximum degree from random lists
Casselgren, Carl Johan
RANDOM STRUCTURES & ALGORITHMS, 2018, 52 (01) : 54 - 73
[47] Coloring random graphs online without creating monochromatic subgraphs
Muetze, Torsten
Rast, Thomas
Spoehe, Reto
PROCEEDINGS OF THE TWENTY-SECOND ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2011, : 145 - 158
[48] RANDOM GRAPHS WITH MONOCHROMATIC TRIANGLES IN EVERY EDGE-COLORING
RODL, V
RUCINSKI, A
RANDOM STRUCTURES & ALGORITHMS, 1994, 5 (02) : 253 - 270
[49] Coloring Random Graphs Online Without Creating Monochromatic Subgraphs
Muetze, Torsten
Rast, Thomas
Spoehel, Reto
RANDOM STRUCTURES & ALGORITHMS, 2014, 44 (04) : 419 - 464
[50] A sharp threshold for random graphs with a monochromatic triangle in every edge coloring
Friedgut, E
Rödl, V
Rucinski, A
Tetali, P
MEMOIRS OF THE AMERICAN MATHEMATICAL SOCIETY, 2006, 179 (845) : III - +

← 1 2 3 4 5 →