Szczegóły publikacji
Opis bibliograficzny
Neighbour sum distinguishing total colourings via the Combinatorial Nullstellensatz / Jakub PRZYBYŁO // Discrete Applied Mathematics ; ISSN 0166-218X. — 2016 — vol. 202, s. 163–173. — Bibliogr. s. 172–173, Abstr. — Publikacja dostępna online od: 2015-09-15
Autor
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 102519 |
|---|---|
| Data dodania do BaDAP | 2016-12-16 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.dam.2015.08.028 |
| Rok publikacji | 2016 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Discrete Applied Mathematics |
Abstract
Consider a simple graph G = (V, E) and its (proper) total colouring c with elements of the set {1, 2, ..., k}. We say that c is neighbour sum distinguishing if for every edge uv is an element of E, the sums of colours met by u and v differ, i.e., c(u) Sigma(e(sic)u) c(e) not equal c(v) + Sigma(e(sic)v). The least k guaranteeing the existence of such a colouring is denoted chi ”(Sigma)(G). We investigate a daring conjecture presuming that chi ”(Sigma)(G) <= Delta(G) + 3 for every graph G, a seemingly demanding problem if confronted with up-to-date progress in research on the Total Colouring Conjecture itself. We note that chi ”(Sigma)(G) <= Delta(G) + 2col(G) 1 and apply Combinatorial Nullstellensatz to prove a stronger bound: chi ”(Sigma)(G) <= Delta(G) + inverted right perpendicular5/3col(G)inverted left perpendicular. This imply an upper bound of the form chi ”(Sigma)(G) <= Delta(G) const. for many classes of graphs with unbounded maximum degree. In particular we obtain chi ”(Sigma) (G) <= Delta(G) + 10 for planar graphs. In fact we show that identicalIounds also hold if we use any set of k real numbers instead of {1, 2, ..., k} as edge colours, and moreover the same is true in list versions of the both concepts. (C) 2015 Elsevier B.V. All rights reserved.
