Szczegóły publikacji
Opis bibliograficzny
Neighbor distinguishing edge colorings via the Combinatorial Nullstellensatz / Jakub PRZYBYŁO // SIAM Journal on Discrete Mathematics ; ISSN 0895-4801. — 2013 — vol. 27 no. 3, s. 1313–1322. — Bibliogr. s. 1321–1322, Abstr.
Autor
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 77268 |
|---|---|
| Data dodania do BaDAP | 2013-11-13 |
| Tekst źródłowy | URL |
| DOI | 10.1137/120880586 |
| Rok publikacji | 2013 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | SIAM Journal on Discrete Mathematics |
Abstract
Consider a simple graph G - (V, E) and its proper edge coloring c with the elements of the set {1, 2, ..., k} (or any other k-element set of real numbers). We say that c is neighbor sum distinguishing if Sigma(w is an element of NG(v)) c(wv) not equal Sigma(w is an element of NG(u)) c(wu) for every edge uv is an element of E. We show that such a coloring exists for any graph G containing no isolated edges if k >= 2 Delta(G)+ col(G) - 1. The proof of this fact is based on iterative applications of the Combinatorial Nullstellensatz. As a consequence, the same number of colors is also sufficient in the well-known corresponding problem, where instead of the sums, we wish to distinguish the sets of colors met by adjacent vertices. In fact we consider list versions of both concepts and prove our assertion in this more general setting.
