Szczegóły publikacji
Opis bibliograficzny
Asymptotically optimal neighbour sum distinguishing colourings of graphs / Jakub PRZYBYŁO // Random Structures & Algorithms ; ISSN 1042-9832. — 2015 — vol. 47 iss. 4, s. 776–791. — Bibliogr. s. 791, Abstr. — Publikacja dostępna online od: 2014-06-09
Autor
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 94956 |
|---|---|
| Data dodania do BaDAP | 2015-12-22 |
| Tekst źródłowy | URL |
| DOI | 10.1002/rsa.20553 |
| Rok publikacji | 2015 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Random Structures & Algorithms |
Abstract
Consider a simple graph G = (V,E) and its proper edge colouring c with the elements of the set {1,2,...,k}. The colouring c is said to be neighbour sum distinguishing if for every pair of vertices u, v adjacent in G, the sum of colours of the edges incident with u is distinct from the corresponding sum for v. The smallest integer k for which such colouring exists is known as the neighbour sum distinguishing index of a graph and denoted by chi'(Sigma)(G). The definition of this parameter, which makes sense for graphs containing no isolated edges, immediately implies that chi'(Sigma)(G) >= Delta, where Delta is the maximum degree of G. On the other hand, it was conjectured by Flandrin et al. that chi'(Sigma)(G) <= Delta + 2 for all those graphs, except for C-5. We prove this bound to be asymptotically correct by showing that chi'(Sigma)(G) <= Delta(1+o(1)). The main idea of our argument relays on a random assignment of the colours, where the choice for every edge is biased by so called attractors, randomly assigned to the vertices.
