×

Conflict-free coloring of graphs. (English) Zbl 1400.05060

Summary: A conflict-free \(k\)-coloring of a graph assigns one of \(k\) different colors to some of the vertices such that, for every vertex \(v\), there is a color that is assigned to exactly one vertex among \(v\) and \(v\)’s neighbors. Such colorings have applications in wireless networking, robotics, and geometry and are well studied in graph theory. Here we study the natural problem of the conflict-free chromatic number \(\chi_{CF}(G)\) (the smallest \(k\) for which conflict-free \(k\)-colorings exist). We provide results both for closed neighborhoods \(N[v]\), for which a vertex \(v\) is a member of its neighborhood, and for open neighborhoods \(N(v)\), for which vertex \(v\) is not a member of its neighborhood. For closed neighborhoods, we prove the conflict-free variant of the famous Hadwiger Conjecture: If an arbitrary graph \(G\) does not contain \(K_{k+1}\) as a minor, then \(\chi_{CF}(G)\leq k\).
For planar graphs, we obtain a tight worst-case bound: three colors are sometimes necessary and always sufficient. In addition, we give a complete characterization of the algorithmic/computational complexity of conflict-free coloring. It is NP-complete to decide whether a planar graph has a conflict-free coloring with one color, while for outerplanar graphs, this can be decided in polynomial time. Furthermore, it is NP-complete to decide whether a planar graph has a conflict-free coloring with two colors, while for outerplanar graphs, two colors always suffice. For the bicriteria problem of minimizing the number of colored vertices subject to a given bound \(k\) on the number of colors, we give a full algorithmic characterization in terms of complexity and approximation for outerplanar and planar graphs. For open neighborhoods, we show that every planar bipartite graph has a conflict-free coloring with at most four colors; on the other hand, we prove that for \(k\in\{1,2,3\}\), it is NP-complete to decide whether a planar bipartite graph has a conflict-free \(k\)-coloring. Moreover, we establish that any general planar graph has a conflict-free coloring with at most eight colors.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C83 Graph minors
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] M. A. Abam, M. de Berg, and S.-H. Poon, Fault-tolerant conflict-free colorings, in Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG), Montreal, Canada, 2008, pp. 13–16.
[2] Z. Abel, V. Alvarez, E. D. Demaine, S. P. Fekete, A. Gour, A. Hesterberg, P. Keldenich, and C. Scheffer, Three colors suffice: Conflict-free coloring of planar graphs, in Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), ACM, New York, SIAM, Philadelphia, 2017, pp. 1951–1963, . · Zbl 1410.05062
[3] D. Ajwani, K. Elbassioni, S. Govindarajan, and S. Ray, Conflict-free coloring for rectangle ranges using \(O(n^{.382})\) colors, in Proceedings of the 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), ACM, New York, 2007, pp. 181–187. · Zbl 1246.68167
[4] J. Alber, M. R. Fellows, and R. Niedermeier, Polynomial-time data reduction for dominating set, J. ACM, 51 (2004), pp. 363–384. · Zbl 1192.68337
[5] N. Alon and S. Smorodinsky, Conflict-free colorings of shallow discs, in Proceedings of the 22nd Symposium on Computational Geometry (SoCG), ACM, New York, 2006, pp. 41–43. · Zbl 1153.68384
[6] K. Appel and W. Haken, Every planar map is four colorable. Part I. Discharging, Illinois J. Math., 21 (1977), pp. 429–490. · Zbl 0387.05009
[7] K. Appel and W. Haken, Every planar map is four colorable. Part II. Reducibility, Illinois J. Math., 21 (1977), pp. 491–567. · Zbl 0387.05010
[8] P. Ashok, A. Dudeja, and S. Kolay, Exact and FPT algorithms for max-conflict free coloring in hypergraphs, in Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC), Springer, Berlin, 2015, pp. 271–282. · Zbl 1391.68087
[9] B. S. Baker and M. Hill, Approximation algorithms for NP-complete problems on planar graphs, J. ACM, 41 (1994), pp. 153–180. · Zbl 0807.68067
[10] A. Bar-Noy, P. Cheilaris, S. Olonetsky, and S. Smorodinsky, Online conflict-free colouring for hypergraphs, Combin. Probab. Comput., 19 (2010), pp. 493–516. · Zbl 1198.05137
[11] P. Cheilaris, L. Gargano, A. A. Rescigno, and S. Smorodinsky, Strong conflict-free coloring for intervals, Algorithmica, 70 (2014), pp. 732–749. · Zbl 1306.05055
[12] P. Cheilaris, S. Smorodinsky, and M. Sulovsky, The potential to improve the choice: List conflict-free coloring for geometric hypergraphs, in Proceedings of the 27th Symposium on Computational Geometry (SoCG), ACM, New York, 2011, pp. 424–432. · Zbl 1283.05191
[13] P. Cheilaris and G. Tóth, Graph unique-maximum and conflict-free colorings, J. Discrete Algorithms, 9 (2011), pp. 241–251. · Zbl 1225.05093
[14] K. Chen, A. Fiat, H. Kaplan, 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 (2006), pp. 1342–1359, . · Zbl 1124.68077
[15] K. Elbassioni and N. H. Mustafa, Conflict-free colorings of rectangles ranges, in Proceedings of the 23rd Symposium on Theoretical Aspects of Computer Science (STACS), Springer, Berlin, 2006, pp. 254–263. · Zbl 1136.68567
[16] 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 (2003), pp. 94–136, . · Zbl 1069.68120
[17] L. Gargano and A. A. Rescigno, Complexity of conflict-free colorings of graphs, Theoret. Comput. Sci., 566 (2015), pp. 39–49. · Zbl 1317.68071
[18] R. Glebov, T. Szabó, and G. Tardos, Conflict-free coloring of graphs, Combin. Probab. Comput., 23 (2014), pp. 434–448. · Zbl 1288.05086
[19] H. Hadwiger, Über eine Klassifikation der Streckenkomplexe, Vierteljahresschrift der Naturforschenden Gesellschaft in Zürich, 88 (1943), pp. 133–143. · Zbl 0061.41308
[20] S. Har-Peled and S. Smorodinsky, Conflict-free coloring of points and simple regions in the plane, Discrete Comput. Geom., 34 (2005), pp. 47–70. · Zbl 1066.05064
[21] F. Hoffmann, K. Kriegel, S. Suri, K. Verbeek, and M. Willert, Tight bounds for conflict-free chromatic guarding of orthogonal art galleries, in Proceedings of the 31st Symposium on Computational Geometry (SoCG), Eindhoven, The Netherlands, 2015, pp. 421–435. · Zbl 1378.68174
[22] E. Horev, R. Krakovski, and S. Smorodinsky, Conflict-free coloring made stronger, in Proceedings of the 12th Scandinavian Symposium and Workshop on Algorithm Theory (SWAT), 2010, pp. 105–117. · Zbl 1284.05100
[23] T. Kikuno, N. Yoshida, and Y. Kakuda, A linear algorithm for the domination number of a series-parallel graph, Discrete Appl. Math., 5 (1983), pp. 299–311. · Zbl 0507.05060
[24] N. Lev-Tov and D. Peleg, Conflict-free coloring of unit disks, Discrete Appl. Math., 157 (2009), pp. 1521–1532. · Zbl 1186.68338
[25] W. Mulzer and G. Rote, Minimum-weight triangulation is NP-hard, J. ACM, 55 (2008), 11. · Zbl 1311.05134
[26] J. Pach and G. Tárdos, Conflict-free colourings of graphs and hypergraphs, Combin. Probab. Comput., 18 (2009), pp. 819–834. · Zbl 1197.05054
[27] N. Robertson, D. Sanders, P. Seymour, and R. Thomas, The four-colour theorem, J. Combin. Theory Ser. B, 70 (1997), pp. 2–44. · Zbl 0883.05056
[28] S. Smorodinsky, Combinatorial Problems in Computational Geometry, Ph.D. thesis, School of Computer Science, Tel Aviv University, Tel Aviv, Israel, 2003.
[29] R. Wilson, Four Colours Suffice: How the Map Problem Was Solved, Princeton University Press, Princeton, NJ, 2013.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.