Szczegóły publikacji
Opis bibliograficzny
On weight choosabilities of graphs with bounded maximum average degree / Jakub PRZYBYŁO, André Raspaud, Mariusz WOŹNIAK // Discrete Applied Mathematics ; ISSN 0166-218X. — 2017 — vol. 217 pt. 3, s. 663–672. — Bibliogr. s. 671–672, Abstr. — Publikacja dostępna online od: 2016-10-20
Autorzy (3)
- AGHPrzybyło Jakub
- Raspaud André
- AGHWoźniak Mariusz
Słowa kluczowe
Dane bibliometryczne
ID BaDAP | 109364 |
---|---|
Data dodania do BaDAP | 2017-10-19 |
Tekst źródłowy | URL |
DOI | 10.1016/j.dam.2016.09.037 |
Rok publikacji | 2017 |
Typ publikacji | artykuł w czasopiśmie |
Otwarty dostęp | |
Czasopismo/seria | Discrete Applied Mathematics |
Abstract
The well known 1-2-3-Conjecture asserts that every connected graph G of order at least three can be edge-coloured with integers 1, 2, 3 so that the sums of colours met by adjacent vertices are distinct in G. The same is believed to hold if instead of edge colourings we consider total colourings assigning 1 or 2 to every vertex and edge of a given graph this time the colour of every vertex is counted in its corresponding sum. We consider list extensions of the both concepts, where every edge (and vertex) is assigned a set of k positive integers, i.e., its potential colours, and regardless of this list assignment we wish to be able to construct a colouring from these lists so that the adjacent vertices are distinguished by their corresponding sums. We prove that if the maximum average degree of the graph is smaller than 5/2, then lists of length k = 3 are sufficient for that goal in case of edge colourings (if G has no isolated edges), while already k = 2 suffices in the total case. In fact the second of these statements remains true with arbitrary real colours admitted instead of positive integers, and the first one for positive reals. The proofs of these facts are based on the discharging method combined with the algebraic approach of Alon known as Combinatorial Nullstellensatz.