Szczegóły publikacji
Opis bibliograficzny
On the neighbor sum distinguishing index of planar graphs / M. Bonamy, J. PRZYBYŁO // Journal of Graph Theory ; ISSN 0364-9024. — 2017 — vol. 85 iss. 3, s. 669–690. — Bibliogr. s. 689–690, Abstr. — Publikacja dostępna online od: 2016-10-20
Autorzy (2)
- Bonamy M.
- AGHPrzybyło Jakub
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 104762 |
|---|---|
| Data dodania do BaDAP | 2017-10-19 |
| Tekst źródłowy | URL |
| DOI | 10.1002/jgt.22098 |
| Rok publikacji | 2017 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Journal of Graph Theory |
Abstract
Let c be a proper edge coloring of a graph G = (V, E) with integers 1, 2,..., k. Then k >= Delta(G), while Vizing's theorem guarantees that we can take k <= Delta(G) + 1. On the course of investigating irregularities in graphs, it has been conjectured that with only slightly larger k, that is, k = Delta(G) + 2, we could enforce an additional strong feature of c, namely that it attributes distinct sums of incident colors to adjacent vertices in G if only this graph has no isolated edges and is not isomorphic to C-5. We prove the conjecture is valid for planar graphs of sufficiently largemaximum degree. In fact an even stronger statement holds, as the necessary number of colors stemming from the result of Vizing is proved to be sufficient for this family of graphs. Specifically, our main result states that every planar graph G of maximum degree at least 28, which contains no isolated edges admits a proper edge coloring c : E -> {1, 2,..., Delta(G) + 1} such that Sigma(e(sic)u) c(e) not equal Sigma(e(sic)u) c(e) for every edge uv of G.
