Weight Choosability of Graphs with Maximum Degree 4  

作　　者：You LU Chong LI Zheng Ke MIAO 

机构地区：[1]School of Mathematics and Statistics and Xi'an-Budapest Joint Research Center for Combinatorics,Northwestern Polytechnical University,Xi'an,710129,P.R.China [2]Department of Mathematics,West Virginia University,Morgantown,WV 26506,USA [3]Research Institute of Mathematical Science and School of Mathematics and Statistics,Jiangsu Normal University,Xuzhou,221116,P.R.China

出　　处：《Acta Mathematica Sinica,English Series》2020年第6期723-732,共10页数学学报（英文版）

基　　金：Supported by National Natural Science Foundation of China(Grant Nos.11871397 and 11971205);the Natural Science Basic Research Plan in Shaanxi Province of China(Grant No.2020JM-083);the Fundamental Research Funds for the Central Universities(Grant No.3102019ghjd003)。

摘　　要：Let k be a positive integer.A graph G is k-weight choosable if,for any assignment L(e)of k real numbers to each e∈E(G),there is a mapping f:E(G)→R such that f(uv)∈L(uv)and∑e∈∂(u)^f(e)≠∑e∈∂(u)^f(e)for each uv∈E(G),where?(v)is the set of edges incident with v.As a strengthening of the famous 1-2-3-conjecture,Bartnicki,Grytczuk and Niwcyk[Weight choosability of graphs.J.Graph Theory,60,242–256(2009)]conjecture that every graph without isolated edge is 3-weight choosable.This conjecture is wildly open and it is even unknown whether there is a constant k such that every graph without isolated edge is k-weight choosable.In this paper,we show that every connected graph of maximum degree 4 is 4-weight choosable.

关 键 词：1-2-3 conjecture weighting weight choosability Combinatorial Nullstellensatz 

分 类 号：O157.5[理学—数学]