Abstract
Let H = (V, E) be a hypergraph. A conflict-free coloring of H is an assignment of colors to V such that, in each hyperedge e ∈ E, there is at least one uniquely-colored vertex. This notion is an extension of the classical graph coloring. Such colorings arise in the context of frequency assignment to cellular antennae, in battery consumption aspects of sensor networks, in RFID protocols, and several other fields. Conflict-free coloring has been the focus of many recent research papers. In this paper, we survey this notion and its combinatorial and algorithmic aspects.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
M. A. Abam, M. de Berg, and S.-H. Poon, Fault-tolerant conflict-free coloring. In Proceedings of the 20th Annual Canadian Conference on Computational Geometry (CCCG), Montreal, Canada, August 13–15, 2008.
M. Abellanas, P. Bose, J. Garcia, F. Hurtado, M. Nicolas, and P. A. Ramos, On properties of higher order delaunay graphs with applications. In EWCG, 2005.
D. Ajwani, K. Elbassioni, S. Govindarajan, and S. Ray, Conflict-free coloring for rectangle ranges using Õ (n·381+ε) colors. In SPAA’ 07: Proc. 19th ACM Symp. on Parallelism in Algorithms and Architectures, pages 181–187, 2007.
N. Alon, Choice numbers of graphs: a probabilistic approach. 1:107–114, 1992.
N. Alon and S. Smorodinsky, Conflict-free colorings of shallow discs, Int. J. Comput. Geometry Appl., 18(6):599–604, 2008.
N. Alon and J. H. Spencer, The Probabilistic Method. Wiely Inter-Science, 2000.
G. Aloupis, J. Cardinal, S. Collette, S. Langerman, and S. Smorodinsky, Coloring geometric range spaces, Discrete & Computational Geometry, 41(2):348–362, 2009.
K. Appel and W. Haken, Every planar map is 4-colorable — 1: Discharging, Illinois Journal of Mathematics, (21):421–490, 1977.
K. Appel and W. Haken, Every planar map is 4-colorable — 2: Reducibility, Illinois Journal of Mathematics, (21):491–567, 1977.
A. Bar-Noy, P. Cheilaris, S. Olonetsky, and S. Smorodinsky, Online conflict-free colouring for hypergraphs, Combinatorics, Probability & Computing, 19(4):493–516, 2010.
A. Bar-Noy, P. Cheilaris, and S. Smorodinsky, Conflict-free coloring for intervals: from offline to online. In Proc. ACM Symposium on Parallelism in Algorithms and Architectures, pages 128–137, New York, NY, USA, 2006. ACM Press.
A. Bar-Noy, P. Cheilaris, and S. Smorodinsky, Deterministic conflict-free coloring for intervals: From offline to online, ACM Transactions on Algorithms, 4(4), 2008.
A. L. Buchsbaum, A. Efrat, S. Jain, S. Venkatasubramanian, and K. Yi, Restricted strip covering and the sensor cover problem. In Proc. Annu. ACM-SIAM Symposium on Discrete Algorithms, pages 1056–1063, 2007.
T. M. Chan, Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set. In Proceedings of the Twenty-eighth Annual Symposium on Computational Geometry, SoCG’ 12, Chapel Hill, North Carolina, USA. ACM (New York, NY, USA, 2012), pp. 293–302.
P. Cheilaris, B. Keszegh, and D. Pálvölgyi, Unique-maximum and conflict-free colorings for hypergraphs and tree graphs, arXiv:1002.4210v1, 2010.
P. Cheilaris, S. Smorodinsky, and M. Sulovský, The potential to improve the choice: list conflict-free coloring for geometric hypergraphs. In Proc. 27th Annu. ACM Sympos. Comput. Geom., 2011.
P. Cheilaris and G. Tóth, Graph unique-maximum and conflict-free colorings. In Proc. 7th International Conference on Algorithms and Complexity (CIAC), pages 143–154, 2010.
K. Chen, A. Fiat, M. Levy, J. Matoušek, E. Mossel, J. Pach, M. Sharir, S. Smorodinsky, U. Wagner, and E. Welzl, Online conflict-free coloring for intervals, Siam. J. Comput., 36:545–554, 2006.
K. Chen, H. Kaplan, and M. Sharir, Online conflict-free coloring for halfplanes, congruent disks, and axis-parallel rectangles, ACM Transactions on Algorithms, 5(2), 2009.
X. Chen, J. Pach, M. Szegedy, and G. Tardos, Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles. In Proc. Annu. ACM-SIAM Symposium on Discrete Algorithms, pages 94–101, 2008.
K. L. Clarkson and P. W. Shor, Application of random sampling in computational geometry, ii, Discrete & Computational Geometry, 4:387–421, 1989.
T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms. MIT Press, Cambridge, MA, 1990.
K. Elbassioni and N. Mustafa, Conflict-free colorings of rectangle ranges. In STACS’ 06: Proc. 23rd International Symposium on Theoretical Aspects of Computer Science, pages 254–263, 2006.
P. Erdős, A. L. Rubin, and H. Taylor, Choosability in graphs. In Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium XXVI, pages 125–157, 1979.
G. Even, Z. Lotker, D. Ron, and S. Smorodinsky, Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks, Siam. J. Comput., 33:94–136, 2003.
M. Gibson and K. R. Varadarajan, Decomposing coverings and the planar sensor cover problem. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25–27, 2009, Atlanta, Georgia, USA, pages 159–168, 2009.
A. Hajnal, I. Juhász, L. Soukup, and Z. Szentmiklóssy, Conflict free colorings of (strongly) almost disjoint set-systems, Acta Mathematica Hungarica, 2011, to appear.
S. Har-Peled and S. Smorodinsky, Conflict-free coloring of points and simple regions in the plane, Discrete & Computational Geometry, 34(1):47–70, 2005.
D. Haussler and E. Welzl, Epsilon-nets and simplex range queries, Discrete & Computational Geometry, 2:127–151, 1987.
E. Horev, R. Krakovski, and S. Smorodinsky, Conflict-free coloring made stronger. In Proc. 12th Scandinavian Symposium and Workshops on Algorithm Theory, 2010.
A. V. Iyer, H. D. Ratliff, and G. Vijayan, Optimal node ranking of trees, Information Processing Letters, 28(5):225–229, 1988.
M. Katchalski, W. McCuaig, and S. M. Seager, Ordered colourings, Discrete Mathematics, 142(1–3):141–154, 1995.
K. Kedem, R. Livne, J. Pach, and M. Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete & Computational Geometry, 1:59–71, 1986.
B. Keszegh, Weak conflict-free colorings of point sets and simple regions. In Proceedings of the 19th Annual Canadian Conference on Computational Geometry, CCCG 2007, August 20–22, 2007, Carleton University, Ottawa, Canada, pages 97–100, 2007.
B. Keszegh, Combinatorial and computational problems about points in the plane. PhD thesis, Central European University, Budapest, Department of Mathematics and its Applications, 2009.
N. Lev-Tov and D. Peleg, Conflict-free coloring of unit disks, Discrete Applied Mathematics, 157(7):1521–1532, 2009.
J. W. H. Liu, Computational models and task scheduling for parallel sparse cholesky factorization, Parallel Computing, 3(4):327–342, 1986.
J. Matoušek, Lectures on Discrete Geometry. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2002.
R. A. Moser and G. Tardos, A constructive proof of the general lovász local lemma, J. ACM, 57(2), 2010.
J. Pach and G. Tardos, Conflict-free colourings of graphs and hypergraphs, Comb. Probab. Comput., 18(5):819–834, 2009.
J. Pach and G. Tardos, Coloring axis-parallel rectangles, Journal of Combinatorial Theory, Series A, in press, 2009.
J. Pach, G. Tardos, and G. Tóth, Indecomposable coverings. In The China-Japan Joint Conference on Discrete Geometry, Combinatorics, and Graph Theory (CJCDGCGT 2005), Lecture Notes in Computer Sceince, pages 135–148, 2007.
J. Pach and G. Tóth, Conflict free colorings, Discrete & Computational Geometry, The Goodman-Pollack Festschrift, pages 665–671, 2003.
J. Pach and G. Tóth, Decomposition of multiple coverings into many parts, Comput. Geom.: Theory and Applications, 42(2):127–133, 2009.
A. A. Schäffer, Optimal node ranking of trees in linear time, Information Processing Letters, 33(2):91–96, 1989.
A. Sen, H. Deng, and S. Guha, On a graph partition problem with application to vlsi layout, Information Processing Letters, 43(2):87–94, 1992.
S. Smorodinsky, Combinatorial Problems in Computational Geometry. PhD thesis, School of Computer Science, Tel-Aviv University, 2003.
S. Smorodinsky, On the chromatic number of some geometric hypergraphs, Siam. J. Discrete Mathematics, 21:676–687, 2007.
S. Smorodinsky, Improved conflict-free colorings of shallow discs, manuscript. 2009.
R. P. Stanley, Combinatorics and Commutative Algebra, Second Edition. Birkhuser, Boston, Inc., 1996.
V. Vizing, Coloring the vertices of a graph in prescribed colors (in russian), Diskret. Analiz., Metody Diskret. Anal. v. Teorii Kodov i Shem 101(29):3–10, 1976.
D. B. West, Introduction to Graph Theory. Prentice Hall, 2ed edition, 2001.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 János Bolyai Mathematical Society and Springer-Verlag
About this chapter
Cite this chapter
Smorodinsky, S. (2013). Conflict-Free Coloring and its Applications. In: Bárány, I., Böröczky, K.J., Tóth, G.F., Pach, J. (eds) Geometry — Intuitive, Discrete, and Convex. Bolyai Society Mathematical Studies, vol 24. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41498-5_12
Download citation
DOI: https://doi.org/10.1007/978-3-642-41498-5_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-41497-8
Online ISBN: 978-3-642-41498-5
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)