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 条
  • [31] COLORING INVARIANTS OF SPATIAL GRAPHS
    Niebrzydowski, Maciej
    JOURNAL OF KNOT THEORY AND ITS RAMIFICATIONS, 2010, 19 (06) : 829 - 841
  • [32] Coloring Graphs with Dense Neighborhoods
    Rabern, Landon
    JOURNAL OF GRAPH THEORY, 2014, 76 (04) : 323 - 340
  • [33] Star Coloring of Sparse Graphs
    Bu, Yuehua
    Cranston, Daniel W.
    Montassier, Mickael
    Raspaud, Andre
    Wang, Weifan
    JOURNAL OF GRAPH THEORY, 2009, 62 (03) : 201 - 219
  • [34] Local edge coloring of graphs
    Deepa, P.
    Srinivasan, P.
    Sundarakannan, M.
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2021, 18 (01) : 29 - 32
  • [35] Clustering and percolation on superpositions of Bernoulli random graphs
    Bloznelis, Mindaugas
    Leskelä, Lasse
    RANDOM STRUCTURES & ALGORITHMS, 2023, 63 (02) : 283 - 342
  • [36] Coloring games on squares of graphs
    Yang, Daqing
    DISCRETE MATHEMATICS, 2012, 312 (08) : 1400 - 1406
  • [37] Coloring powers of planar graphs
    Agnarsson, G
    Halldórsson, MM
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2003, 16 (04) : 651 - 662
  • [38] Coloring Fiber Product of Graphs
    Carbonneaux, Yves
    Gravier, Sylvain
    Khelladi, Abdelkader
    Semri, Ahmed
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2006, 3 (01) : 59 - 64
  • [39] Coloring distance graphs on the plane
    Chybowska-Sokol, Joanna
    Junosza-Szaniawski, Konstanty
    Wesek, Krzysztof
    DISCRETE MATHEMATICS, 2023, 346 (07)
  • [40] The independence coloring game on graphs
    Bresar, Bostjan
    Stesl, Dasa
    QUAESTIONES MATHEMATICAE, 2022, 45 (09) : 1413 - 1434
12345