Hostname: page-component-745bb68f8f-l4dxg Total loading time: 0 Render date: 2025-02-06T21:55:18.375Z 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: roman.l.glebov@gmail.com)
TIBOR SZABÓ
Affiliation:
Institute of Mathematics, Free University of Berlin, 14195 Berlin, Germany (e-mail: szabo@math.fu-berlin.de)
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: tardos@renyi.hu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 

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