Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1137/050647153 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
random graph,chromatic number,high probability,coloring random intersection graphs,complex networks,certain range,real network data,positive theoretical prediction,different greedy algorithm,mutual optimality,random intersection graph,intersection graph,greedy algorithm,complex network | Discrete mathematics,Random regular graph,Indifference graph,Combinatorics,Random graph,Chordal graph,Intersection graph,Brooks' theorem,Greedy coloring,Mathematics,Critical graph | Journal |
Volume | Issue | ISSN |
23 | 1 | 0895-4801 |
Citations | PageRank | References |
12 | 1.53 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Behrisch | 1 | 49 | 8.77 |
| Anusch Taraz | 2 | 168 | 37.71 |
| Michael Ueckerdt | 3 | 12 | 1.53 |