Geodesic
Worm Colorings
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 3, pp. 571-584.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: coloring, rainbow, monochromatic, forbidden, path 
@article{DMGT_2015_35_3_a13,
     author = {Goddard, Wayne and Wash, Kirsti and Xu, Honghai},
     title = {Worm {Colorings}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {571--584},
     publisher = {mathdoc},
     volume = {35},
     number = {3},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a13/}
}
TY  - JOUR
AU  - Goddard, Wayne
AU  - Wash, Kirsti
AU  - Xu, Honghai
TI  - Worm Colorings
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 571
EP  - 584
VL  - 35
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a13/
LA  - en
ID  - DMGT_2015_35_3_a13
ER  - 
%0 Journal Article
%A Goddard, Wayne
%A Wash, Kirsti
%A Xu, Honghai
%T Worm Colorings
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 571-584
%V 35
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a13/
%G en
%F DMGT_2015_35_3_a13
Goddard, Wayne; Wash, Kirsti; Xu, Honghai. Worm Colorings. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 3, pp. 571-584. http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a13/

[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

[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

[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

[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

[5] R. Cowen, Some connections between set theory and computer science, Lecture Notes in Comput. Sci. 713 (1993) 14-22. doi:10.1007/BFb0022548

[6] W. Goddard, K. Wash and H. Xu, WORM colorings forbidding cycles or cliques, Congr. Numer. 219 (2014) 161-173.

[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

[8] L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar. 1 (1966) 237-238.

[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

[10] Zs. Tuza, Graph colorings with local constraints-a survey, Discuss. Math. Graph Theory 17 (1997) 161-228. doi:10.7151/dmgt.1049