Szczegóły publikacji
Opis bibliograficzny
Neighbor distinguishing edge colorings via the Combinatorial Nullstellensatz revisited / Jakub PRZYBYŁO, Tsai-Lien Wong // Journal of Graph Theory ; ISSN 0364-9024. — 2015 — vol. 80 iss. 4, s. 299–312. — Bibliogr. s. 311–312, Abstr.
Autorzy (2)
- AGHPrzybyło Jakub
- Wong Tsai-Lien
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 93983 |
|---|---|
| Data dodania do BaDAP | 2015-11-24 |
| Tekst źródłowy | URL |
| DOI | 10.1002/jgt.21852 |
| Rok publikacji | 2015 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Journal of Graph Theory |
Abstract
Consider a simple graph G=(V,E) and its proper edge coloring c with the elements of the set {1,⋯,k}. We say that c is neighbor set distinguishing (or adjacent strong) if for every edge uvεE, the set of colors incident with u is distinct from the set of colors incident with v. Let us then consider a stronger requirement and suppose we wish to distinguishing adjacent vertices by sums of their incident colors. In both problems the challenging conjectures presume that such colorings exist for any graph G containing no isolated edges if only k≥Δ(G)+2. We prove that in both problems k=Δ(G)+3 col (G)-4 is sufficient. The proof is based on the Combinatorial Nullstellensatz, applied in the "sum environment." In fact the identical bound also holds if we use any set of k real numbers instead of {1, ⋯,k} as edge colors, and the same is true in list versions of the both concepts. In particular, we therefore obtain that lists of length Δ(G)+14 (Δ(G)+13 in fact) are sufficient for planar graphs.
