PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2015 | 35 | 3 | 571-584
Tytuł artykułu

Worm Colorings

Treść / Zawartość
Warianty tytułu
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
Wydawca
Rocznik
Tom
35
Numer
3
Strony
571-584
Opis fizyczny
Daty
wydano
2015-08-01
otrzymano
2014-06-05
poprawiono
2014-11-17
zaakceptowano
2014-11-17
online
2015-07-29
Twórcy
autor
autor
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]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1814
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.