Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-25T09:19:24.705Z Has data issue: false hasContentIssue false
  • English
  • Français

Conflict-Free Colouring of Graphs

Published online by Cambridge University Press:  29 November 2013

ROMAN GLEBOV ,
TIBOR SZABÓ  and
GÁBOR TARDOS
ROMAN GLEBOV
Affiliation:
Department of Mathematics, ETH, 8092 Zurich, Switzerland and Mathematics Institute and DIMAP, University of Warwick, Coventry CV4 7AL, UK (e-mail: [email protected])
TIBOR SZABÓ
Affiliation:
Institute of Mathematics, Free University of Berlin, 14195 Berlin, Germany (e-mail: [email protected])
GÁBOR TARDOS
Affiliation:
Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary and Zhejiang Normal University, Jinhua, China (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We study the conflict-free chromatic number χCF of graphs from extremal and probabilistic points of view. We resolve a question of Pach and Tardos about the maximum conflict-free chromatic number an n-vertex graph can have. Our construction is randomized. In relation to this we study the evolution of the conflict-free chromatic number of the Erdős–Rényi random graph G(n,p) and give the asymptotics for p = ω(1/n). We also show that for p ≥ 1/2 the conflict-free chromatic number differs from the domination number by at most 3.

Keywords

Primary 05C15Secondary 05C3505C8005D4005C69
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 23 , Issue 3 , May 2014 , pp. 434 - 448
Copyright
Copyright © Cambridge University Press 2013 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Alon, N., Bar-Noy, A., Linial, N. and Peleg, D. (1991) A lower bound for radio broadcast. J. Comput. System Sci. 43 290–298.Google Scholar
[2]Bar-Yehuda, R., Goldreich, O. and Itai, A. (1986) On the time-complexity of broadcast in radio networks: An exponential gap between determinism and randomization. In Proc. 4th ACM Symposium on Principles of Distributed Computing, pp. 98–107.Google Scholar
[3]Bollobás, B. (2001) Random Graphs, second edition, Academic Press.CrossRefGoogle Scholar
[4]Even, G., Lotker, Z., Ron, D. and Smorodinsky, S. (2003) Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. SIAM J. Comput. 33 94–136.Google Scholar
[5]Glebov, R., Liebenau, A. and Szabó, T. Concentration of the domination number of the random graph. Submitted. http://arxiv.org/pdf/1209.3115v3.pdfGoogle Scholar
[6]Łuczak, T. (1991) Size and connectivity of the k-core of a random graph. Discrete Math. 91 61–68.Google Scholar
[7]Pach, J. and Tardos, G. (2009) Conflict-free colorings of graphs and hypergraphs. Combin. Probab. Comput. 18 819–834.Google Scholar
[8]Pittel, B., Spencer, J. and Wormald, N. C. (1996) Sudden emergence of a giant k-core in a random graph. J. Combin. Theory Ser. B 67 111–151.CrossRefGoogle Scholar
[9]Smorodinsky, S. (2003) Combinatorial problems in computational geometry. PhD Dissertation, School of Computer Science, Tel Aviv University.Google Scholar
[10]Smorodinsky, S.Conflict-free coloring and its applications. In Geometry: Intuitive, Discrete, and Convex (Bárány, I., Böröczky, K. J., Fejes Tóth, G. and Pach, J., eds), Vol. 24 of Bolyai Society Mathematical Studies, Springer. To appear. http://arxiv.org/pdf/1005.3616.pdfGoogle Scholar
[11]Wieland, B. and Godbole, A. P. (2001) On the domination number of a random graph. Electron. J. Combin. 8 R37.Google Scholar