Worm Colorings

• Autorzy: Wayne Goddard , Kirsti Wash , Honghai Xu
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

coloring; rainbow; monochromatic; forbidden; path.

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2015
• Tom: 35
• Numer: 3
• Strony: 571-584

Daty

wydano

2015-08-01

otrzymano

2014-06-05

poprawiono

2014-11-17

zaakceptowano

2014-11-17

online

2015-07-29

Twórcy

autor

Wayne Goddard

• Department of Mathematical Sciences Clemson University, USA

autor

Kirsti Wash

• Department of Mathematics Trinity College CN, USA

autor

Honghai Xu

• Department of Mathematical Sciences Clemson University, USA

Bibliografia

• [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]
• [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]
• [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]
• [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]
• [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]
• [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[Crossref]
• [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[Crossref]
• [10] Zs. Tuza, Graph colorings with local constraints-a survey, Discuss. Math. Graph Theory 17 (1997) 161-228. doi:10.7151/dmgt.1049 [Crossref]

Identyfikatory

DOI

10.7151/dmgt.1814