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 条
  • [21] Random complex networks
    Small, Michael
    Hou, Lvlin
    Zhang, Linjun
    NATIONAL SCIENCE REVIEW, 2014, 1 (03) : 357 - 367
  • [22] SECRECY TRANSFER FOR SENSOR NETWORKS: FROM RANDOM GRAPHS TO SECURE RANDOM GEOMETRIC GRAPHS
    Liu, Zhihong
    Ma, Jianfeng
    Zeng, Yong
    INTERNATIONAL JOURNAL ON SMART SENSING AND INTELLIGENT SYSTEMS, 2013, 6 (01): : 77 - 94
  • [23] Indicated coloring of graphs
    Grzesik, Andrzej
    DISCRETE MATHEMATICS, 2012, 312 (23) : 3467 - 3472
  • [24] Coloring Artemis graphs
    Leveque, Benjamin
    Maffray, Frederic
    Reed, Bruce
    Trotignon, Nicolas
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (21-23) : 2234 - 2240
  • [25] Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree
    de Gevigney, Olivier Durand
    Meunier, Frederic
    Popa, Christian
    Reygner, Julien
    Romero, Ayrin
    4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2011, 9 (02): : 175 - 188
  • [26] Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree
    Olivier Durand de Gevigney
    Frédéric Meunier
    Christian Popa
    Julien Reygner
    Ayrin Romero
    4OR, 2011, 9 : 175 - 188
  • [27] Watermarking Graph Neural Networks by Random Graphs
    Zhao, Xiangyu
    Wu, Hanzhou
    Zhang, Xinpeng
    9TH INTERNATIONAL SYMPOSIUM ON DIGITAL FORENSICS AND SECURITY (ISDFS'21), 2021,
  • [28] Dominator coloring and CD coloring in almost cluster graphs ☆
    Banik, Aritra
    Kasthurirangan, Prahlad Narasimhan
    Raman, Venkatesh
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2025, 150
  • [29] On the hyperbolicity of bipartite graphs and intersection graphs
    Coudert, David
    Ducoffe, Guillaume
    DISCRETE APPLIED MATHEMATICS, 2016, 214 : 187 - 195
  • [30] Coloring random triangulations
    Di Francesco, P
    Eynard, B
    Guitter, E
    NUCLEAR PHYSICS B, 1998, 516 (03) : 543 - 587
12345