Dynamic \(F\)-free coloring of graphs. (English) Zbl 1397.05059
Summary: A problem of graph \(F\)-free coloring consists in partitioning the vertex set of a graph such that none of the resulting sets induces a graph containing a fixed graph \(F\) as an induced subgraph. In this paper we consider dynamic \(F\)-free coloring in which, similarly as in online coloring, the graph to be colored is not known in advance; it is gradually revealed to the coloring algorithm that has to color each vertex upon request as well as handle any vertex recoloring requests. Our main concern is the greedy approach and characterization of graph classes for which it is possible to decide in polynomial time whether for the fixed forbidden graph \(F\) and positive integer \(k\) the greedy algorithm ever uses more than \(k\) colors in dynamic \(F\)-free coloring. For various classes of graphs we give such characterizations in terms of a finite number of minimal forbidden graphs thus solving the above-mentioned problem for the so-called \(F\)-trees when \(F\) is 2-connected, and for classical trees, when \(F\) is a path of order 3 (the latter variant is also known as subcoloring or 1-improper coloring).
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C75 | Structural characterization of families of graphs |
Software:
CriticalPfreeGraphsReferences:
| [1] | Achlioptas, D.: The complexity of \[G\] G-free colourability. Discret. Math. 165(166), 21-30 (1997) · Zbl 0904.05030 · doi:10.1016/S0012-365X(97)84217-3 |
| [2] | Albertson, M.O., Jamison, R.E., Hedetniemi, S.T., Locke, S.C.: The subchromatic number of a graph. Discret. Math. 74, 33-49 (1989) · Zbl 0681.05033 · doi:10.1016/0012-365X(89)90196-9 |
| [3] | Araujo, J., Linhares-Sales, C.: On the Grundy number of graphs with few \[P_4\] P4’s. Discret. Appl. Math. 160, 2514-2522 (2012) · Zbl 1296.05065 · doi:10.1016/j.dam.2011.08.016 |
| [4] | Bermond, J.-C., Havet, F., Huc, F., Linhares-Sales, C.: Improper coloring of weighted grid and hexagonal graphs. Discret. Math. Algorithm Appl. 2, 395-412 (2010) · Zbl 1201.05034 · doi:10.1142/S1793830910000747 |
| [5] | Borowiecki, P., Rautenbach, D.: New potential functions for greedy independence and coloring. Discret. Appl. Math. 182, 61-72 (2015) · Zbl 1306.05175 · doi:10.1016/j.dam.2013.12.011 |
| [6] | Borowiecki, P.: Computational aspects of greedy partitioning of graphs. J. Comb. Optim. 35(2), 641-665 (2018). https://doi.org/10.1007/s10878-017-0185-2 · Zbl 1385.68016 · doi:10.1007/s10878-017-0185-2 |
| [7] | Borowiecki, P., Sidorowicz, E.: Dynamic coloring of graphs. Fund. Inf. 114, 105-128 (2012) · Zbl 1236.05077 |
| [8] | Broere, I., Mynhardt, C.M.: Generalized Colorings of Graphs. Graph Theory with Applications to Algorithms and Computer Science, (Kalamazoo, 1984). Wiley, New York (1985) · Zbl 0572.05028 |
| [9] | Broersma, H., Fomin, F., Kratochvíl, J., Woeginger, G.J.: Planar graph coloring avoiding monochromatic subgraphs: trees and paths make it difficult. Algorithmica 44, 343-361 (2006) · Zbl 1095.68075 · doi:10.1007/s00453-005-1176-8 |
| [10] | Caramia, M., Dell’Olmo, P.: Iterative coloring extension of a maximum clique. Naval Res. Log. 48, 518-549 (2001) · Zbl 1009.90121 · doi:10.1002/nav.1033 |
| [11] | Chartrand, G., Geller, D., Hedetniemi, S.: A generalization of chromatic number. Proc. Camb. Philos. Soc. 64, 265-271 (1968) · Zbl 0173.26204 · doi:10.1017/S0305004100042808 |
| [12] | Chartrand, G., Zhang, P.: Chromatic Graph Theory. Discrete Mathematics and its Applications. Chapman and Hall/CRC Press, Boca Raton (2008) · Zbl 1169.05001 · doi:10.1201/9781584888017 |
| [13] | Christen, C.A., Selkow, S.M.: Some perfect coloring properties of graphs. J. Combin. Theory Ser. B 27, 49-59 (1979) · Zbl 0427.05033 · doi:10.1016/0095-8956(79)90067-4 |
| [14] | Chudnovsky, M., Goedgebeur, J., Schaudt, O., Zhong, M.: Obstructions for three-coloring graphs with one forbidden induced subgraph. In: Proceedings of 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’16, pp. 1774-1783 (2016) · Zbl 1410.05063 |
| [15] | Cowen, L., Cowen, R.H., Woodall, D.R.: Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency. J. Graph Theory 10, 187-195 (1986) · Zbl 0596.05024 · doi:10.1002/jgt.3190100207 |
| [16] | Fiala, J., Jansen, K., Le, V.B., Seidel, E.: Graph subcolorings: complexity and algorithms. SIAM J. Discret. Math. 16, 636-650 (2003) · Zbl 1029.05052 · doi:10.1137/S0895480101395245 |
| [17] | Gimbel, J., Hartman, C.: Subcolorings and the subchromatic number of a graph. Discret. Math. 272, 139-154 (2003) · Zbl 1028.05032 · doi:10.1016/S0012-365X(03)00177-8 |
| [18] | Gimbel, J., Nešetřil, J.: On partitions of graphs into cographs. Discret. Math. 310, 3437-3445 (2010) · Zbl 1209.05181 · doi:10.1016/j.disc.2010.07.011 |
| [19] | Goedgebeur, J., Schaudt, O.: Exhaustive generation of \[k\] k-critical \[{\cal{H}}H\]-free graphs. In: Proceedings of Graph-Theoretic Concepts in Computer Science—42nd International Workshop, WG’16, pp. 109-120 (2016) · Zbl 1417.05066 |
| [20] | Goyal, N., Vishwanathan, S.: NP-completeness of undirected Grundy numberings and related problems. Unpublished manuscript (1998) |
| [21] | Havet, F., Kang, R.J., Sereni, J.-S.: Improper coloring of unit disk graphs. Networks 54, 150-164 (2009) · Zbl 1207.05056 · doi:10.1002/net.20318 |
| [22] | Hedetniemi, S.M., Hedetniemi, S.T., Beyer, T.: A linear algorithm for the Grundy (coloring) number of a tree. Congr. Numer. 36, 351-363 (1982) · Zbl 0507.68038 |
| [23] | Hoàng, C.T., Le, \[V.B.: P_4\] P4-free colorings and \[P_4\] P4-bipartite graphs. Discret. Math. Theor. Comput. Sci. 4, 109-122 (2001) · Zbl 0965.05041 |
| [24] | Hoàng, C.T., Moore, B., Recoskie, D., Sawada, J., Vatshelle, M.: Constructions of \[k\] k-critical \[P_5\] P5-free graphs. Discret. Appl. Math. 182, 91-98 (2015) · Zbl 1306.05061 · doi:10.1016/j.dam.2014.06.007 |
| [25] | Jensen, T.R., Toft, B.: Graph Coloring Problems. Willey, New Jersey (1995) · Zbl 0855.05054 |
| [26] | Molloy, M.S., Reed, B.: Graph Colouring and the Probabilistic Method. Algorithms and Combinatorics, vol. 23. Springer, New York (2002) · Zbl 0987.05002 |
| [27] | Newman, M.E.J.: Networks: An introduction. Oxford University Press, Oxford (2010) · Zbl 1195.94003 · doi:10.1093/acprof:oso/9780199206650.001.0001 |
| [28] | Zaker, M.: Results on the Grundy chromatic number of graphs. Discret. Math. 306, 3166-3173 (2006) · Zbl 1105.05027 · doi:10.1016/j.disc.2005.06.044 |
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.
