Given a coloring of the vertices, we say subgraph H is monochromatic if every vertex of H is assigned the same color, and rainbow if no pair of vertices of H are assigned the same color. Given a graph G and a graph F, we define an F-WORM coloring of G as a coloring of the vertices of G without a rainbow or monochromatic subgraph H isomorphic to F. We present some results on this concept especially as regards to the existence, complexity, and optimization within certain graph classes. The focus is on the case that F is the path on three vertices.
@article{bwmeta1.element.doi-10_7151_dmgt_1814,
author = {Wayne Goddard and Kirsti Wash and Honghai Xu},
title = {Worm Colorings},
journal = {Discussiones Mathematicae Graph Theory},
volume = {35},
year = {2015},
pages = {571-584},
zbl = {1317.05055},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1814}
}
Wayne Goddard; Kirsti Wash; Honghai Xu. Worm Colorings. Discussiones Mathematicae Graph Theory, Tome 35 (2015) pp. 571-584. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1814/
[1] M. Axenovich and P. Iverson, Edge-colorings avoiding rainbow and monochromatic subgraphs, Discrete Math. 308 (2008) 4710-4723. doi:10.1016/j.disc.2007.08.092[Crossref][WoS] | Zbl 1235.05092
[2] M. Axenovich, T. Jiang and A. Kündgen, Bipartite anti-Ramsey numbers of cycles, J. Graph Theory 47 (2004) 9-28. doi:10.1002/jgt.20012[Crossref] | Zbl 1062.05095
[3] Cs. Bujtás, E. Sampathkumar, Zs. Tuza, C. Dominic and L. Pushpalatha, Vertex coloring without large polychromatic stars, Discrete Math. 312 (2012) 2102-2108. doi:10.1016/j.disc.2011.04.013[WoS][Crossref] | Zbl 1244.05088
[4] Cs. Bujtás, E. Sampathkumar, Zs. Tuza, M.S. Subramanya and C. Dominic, 3- consecutive C-colorings of graphs, Discuss. Math. Graph Theory 30 (2010) 393-405. doi:10.7151/dmgt.1502[Crossref] | Zbl 1217.05087
[5] R. Cowen, Some connections between set theory and computer science, Lecture Notes in Comput. Sci. 713 (1993) 14-22. doi:10.1007/BFb0022548[Crossref] | Zbl 0794.03072
[6] W. Goddard, K. Wash and H. Xu, WORM colorings forbidding cycles or cliques, Congr. Numer. 219 (2014) 161-173. | Zbl 1312.05050
[7] S.M. Hedetniemi, A. Proskurowski and M.M. Sys lo, Interior graphs of maximal outerplane graphs, J. Combin. Theory Ser.B 38 (1985) 156-167. doi:10.1016/0095-8956(85)90081-4[Crossref]
[8] L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar. 1 (1966) 237-238. | Zbl 0151.33401
[9] J.A. Telle and A. Proskurowski, Algorithms for vertex partitioning problems on par- tial k-trees, SIAM J. Discrete Math. 10 (1997) 529-550. doi:10.1137/S0895480194275825[Crossref] | Zbl 0885.68118
[10] Zs. Tuza, Graph colorings with local constraints-a survey, Discuss. Math. Graph Theory 17 (1997) 161-228. doi:10.7151/dmgt.1049 [Crossref] | Zbl 0923.05027