COLORING RANDOM INTERSECTION GRAPHS AND COMPLEX NETWORKS

被引：14
|
作者：
Behrisch, Michael [1 ]
Taraz, Anusch [2 ]
Ueckerdt, Michael [1 ]
机构：
[1] Humboldt Univ, Inst Informat, D-10099 Berlin, Germany
[2] Tech Univ Munich, Zentrum Math, D-80290 Munich, Germany
来源：
SIAM JOURNAL ON DISCRETE MATHEMATICS | 2009年 / 23卷 / 01期
关键词：
coloring; intersection graph; random graph; complex network;
D O I：
10.1137/050647153
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
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 colored 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.
引用
收藏
页码：288 / 299
页数：12
相关论文
共 50 条
  • [1] On-line coloring of geometric intersection graphs
    Erlebach, T
    Fiala, J
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2002, 23 (02): : 243 - 255
  • [2] Coloring the complements of intersection graphs of geometric figures
    Kim, Seog-Jin
    Nakprasit, Kittikorn
    DISCRETE MATHEMATICS, 2008, 308 (20) : 4589 - 4594
  • [3] On MAXCUT in strictly supercritical random graphs, and coloring of random graphs and random tournaments
    Gishholiner, Lior
    Krivelevich, Michael
    Kronenberg, Gal
    RANDOM STRUCTURES & ALGORITHMS, 2018, 52 (04) : 545 - 559
  • [4] COMPONENT EVOLUTION IN GENERAL RANDOM INTERSECTION GRAPHS
    Bloznelis, Mindaugas
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 24 (02) : 639 - 654
  • [5] Clique coloring of dense random graphs
    Alon, Noga
    Krivelevich, Michael
    JOURNAL OF GRAPH THEORY, 2018, 88 (03) : 428 - 433
  • [6] Assortativity and clustering of sparse random intersection graphs
    Bloznelis, Mindaugas
    Jaworski, Jerzy
    Kurauskas, Valentas
    ELECTRONIC JOURNAL OF PROBABILITY, 2013, 18 : 1 - 24
  • [7] A note on Hamiltonicity of uniform random intersection graphs
    Mindaugas Bloznelis
    Irmantas Radavičius
    Lithuanian Mathematical Journal, 2011, 51 : 155 - 161
  • [8] A NOTE ON HAMILTONICITY OF UNIFORM RANDOM INTERSECTION GRAPHS
    Bloznelis, Mindaugas
    Radavicius, Irmantas
    LITHUANIAN MATHEMATICAL JOURNAL, 2011, 51 (02) : 155 - 161
  • [9] Scaling laws for maximum coloring of random geometric graphs
    Borst, Sem
    Bradonjic, Milan
    DISCRETE APPLIED MATHEMATICS, 2017, 217 : 427 - 437
  • [10] Modeling interest-based social networks: Superimposing Erdos-Renyi graphs over random intersection graphs
    Zhao, Jun
    2017 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP), 2017, : 3704 - 3708
12345