Paper Info
Title
On weight choosabilities of graphs with bounded maximum average degree.
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 G 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.
Year
DOI
Venue
2017
10.1016/j.dam.2016.09.037
Discrete Applied Mathematics
Keywords
Field
DocType
1–2–3 Conjecture,1–2-Conjecture,3-edge-weight choosability,2-total weight choosability,Combinatorial Nullstellensatz,Discharging method,Maximum average degree
Discharging method,Integer,Discrete mathematics,Combinatorics,Algebraic number,Vertex (geometry),Neighbourhood (graph theory),Mathematical proof,Connectivity,Mathematics,Bounded function
Journal
Volume
Issue
ISSN
217
P3
0166-218X
Citations 
PageRank 
References 
1
0.39
6
Authors
3
Name
Order
Citations
PageRank
Jakub Przybyło121027.55
André Raspaud285085.91
Mariusz Woźniak320434.54