# Worm Colorings

Wayne Goddard; Kirsti Wash; Honghai Xu

Discussiones Mathematicae Graph Theory (2015)

- Volume: 35, Issue: 3, page 571-584
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topWayne Goddard, Kirsti Wash, and Honghai Xu. "Worm Colorings." Discussiones Mathematicae Graph Theory 35.3 (2015): 571-584. <http://eudml.org/doc/271211>.

@article{WayneGoddard2015,

abstract = {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.},

author = {Wayne Goddard, Kirsti Wash, Honghai Xu},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {coloring; rainbow; monochromatic; forbidden; path.; path},

language = {eng},

number = {3},

pages = {571-584},

title = {Worm Colorings},

url = {http://eudml.org/doc/271211},

volume = {35},

year = {2015},

}

TY - JOUR

AU - Wayne Goddard

AU - Kirsti Wash

AU - Honghai Xu

TI - Worm Colorings

JO - Discussiones Mathematicae Graph Theory

PY - 2015

VL - 35

IS - 3

SP - 571

EP - 584

AB - 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.

LA - eng

KW - coloring; rainbow; monochromatic; forbidden; path.; path

UR - http://eudml.org/doc/271211

ER -

## References

top- [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] Zbl1235.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] Zbl1062.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] Zbl1244.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] Zbl1217.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] Zbl0794.03072
- [6] W. Goddard, K. Wash and H. Xu, WORM colorings forbidding cycles or cliques, Congr. Numer. 219 (2014) 161-173. Zbl1312.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. Zbl0151.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] Zbl0885.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] Zbl0923.05027

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.