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 条
  • [41] GLOBAL DOMINATOR COLORING OF GRAPHS
    Hamid, Ismail Sahul
    Rajeswari, Malairaj
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2019, 39 (02) : 325 - 339
  • [42] Coloring Graphs with Constraints on Connectivity
    Aboulker, Pierre
    Brettell, Nick
    Havet, Frederic
    Marx, Daniel
    Trotignon, Nicolas
    JOURNAL OF GRAPH THEORY, 2017, 85 (04) : 814 - 838
  • [43] Isoperimetric Numbers of Randomly Perturbed Intersection Graphs
    Shang, Yilun
    SYMMETRY-BASEL, 2019, 11 (04):
  • [44] On the dominator coloring in proper interval graphs and block graphs
    Panda, B. S.
    Pandey, Arti
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2015, 7 (04)
  • [45] Max-Coloring and Online Coloring with Bandwidths on Interval Graphs
    Pemmaraju, Sriram V.
    Raman, Rajiv
    Varadarajan, Kasturi
    ACM TRANSACTIONS ON ALGORITHMS, 2011, 7 (03)
  • [46] Coloring immersion-free graphs
    Kakimura, Naonori
    Kawarabayashi, Ken-ichi
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2016, 121 : 284 - 307
  • [47] Coloring quasi-line graphs
    Chudnovsky, Maria
    Ovetsky, Alexandra
    JOURNAL OF GRAPH THEORY, 2007, 54 (01) : 41 - 50
  • [48] The Characterization of Lucky Edge Coloring in Graphs
    Anantayasethi, A.
    Koppitz, J.
    Worawiset, S.
    Saengsura, K.
    ASIAN-EUROPEAN JOURNAL OF MATHEMATICS, 2023, 16 (07)
  • [49] On the conjectures of neighbor locating coloring of graphs
    Mojdeh, Doost Ali
    THEORETICAL COMPUTER SCIENCE, 2022, 922 : 300 - 307
  • [50] Parameterized coloring problems on chordal graphs
    Marx, D
    THEORETICAL COMPUTER SCIENCE, 2006, 351 (03) : 407 - 424
12345