Abstract
Let \(G=(V,E)\) be a finite connected graph along with a coloring of the vertices of G using the colors in a given set X. In this paper, we introduce multi-color forcing, a generalization of zero-forcing on graphs, and give conditions in which the multi-color forcing process terminates regardless of the number of colors used. We give an upper bound on the number of steps required to terminate a forcing procedure in terms of the number of vertices in the graph on which the procedure is being applied. We then focus on multi-color forcing with three colors and analyze the end states of certain families of graphs, including complete graphs, complete bipartite graphs, and paths, based on various initial colorings. We end with a few directions for future research.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
AIM Minimum Rank-Special Graphs Work Group.: Zero forcing sets and the minimum rank of graphs. Linear Algebra Appl. 428(7), 1628–1648 (2008). https://doi.org/10.1016/j.laa.2007.10.009
Barioli, F., Barrett, W., Fallat, S.M., Hall, H.T., Hogben, L., Shader B., van den Driessche, P., van der Holst, H.: Zero forcing parameters and minimum rank problems. Linear Algebra Appl. 433(2), 401–411 (2010). https://doi.org/10.1016/j.laa.2010.03.008
Barioli, F., Barrett, W., Fallat, S.M., Hall, H.T., Hogben, L., Shader, B., van den Driessche, P., van der vaHolst, H.: Parameters related to tree-width, zero forcing and maximum nullity of a graph. J. Graph Theory 72(2), 146–177 (2013). https://doi.org/10.1002/jgt.21637
Burgarth D, Giovannetti, V.: Full control by locally induced relaxation. Phys. Rev. Lett. 99, 10 (2007). https://doi.org/10.1103/PhysRevLett.99.100501
Chilakamarri, K.B., Dean, N., Kang, C.X., Yi, E.: Iteration index of a zero forcing set in a graph. Bull. Inst. Combin Appl. 64, 57–72 (2012)
Dreyer Jr., P.A., Robert, F.S.: Irreversible \(k\)-threshold processes: graph-theoretical threshold models of the spread of disease and of opinion. Discrete Appl. Math. 157(7), 1615–1627 (2009). https://doi.org/10.1016/j.dam.2008.09.012
Edholm, C.J., Hogben, L., Huynh, M., LaGrange, J., Row, D.D.: Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph. Linear Algebra Appl. 436(12), 4352–4372 (2012). https://doi.org/10.1016/j.laa.2010.10.015
Hogben, L., Huynh, M., Kingsley, N., Meyer, S., Walker, S., Young, M.: Propagation time for zero forcing on a graph. Discrete Appl. Math. 160(13–14), 1994–2005 (2012). https://doi.org/10.1016/j.dam.2012.04.003
Huang, L.-H., Chang, G.J., Yeh, H.-G.: On minimum rank and zero forcing sets of a graph. Linear Algebra Appl. 432(11), 2961–2973 (2010). https://doi.org/10.1016/j.laa.2010.01.001
Kalinowski, T., Kamčev, N., Sudakov, B.: The zero forcing number of graphs. SIAM J. Discrete Math. 33(1), 95–115 (2019). https://doi.org/10.1137/17M1133051
Misc zero forcing and its applications. American Institute of Mathematics. http://aimpl.org/zeroforcing/1/
Acknowledgements
The authors thank Minerva Catral for introducing them to this problem.
Funding
P. E. Harris was supported in part by the National Science Foundation Grant DMS-1620202.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Bozeman, C., Harris, P.E., Jain, N. et al. Multi-color Forcing in Graphs. Graphs and Combinatorics 36, 1855–1868 (2020). https://doi.org/10.1007/s00373-020-02201-9
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-020-02201-9