کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419265 683763 2016 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Neighbour sum distinguishing total colourings via the Combinatorial Nullstellensatz
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Neighbour sum distinguishing total colourings via the Combinatorial Nullstellensatz
چکیده انگلیسی

Consider a simple graph G=(V,E)G=(V,E) and its (proper) total colouring cc with elements of the set {1,2,…,k}{1,2,…,k}. We say that cc is neighbour sum distinguishing   if for every edge uv∈Euv∈E, the sums of colours met by uu and vv differ, i.e.,  c(u)+∑e∋uc(e)≠c(v)+∑e∋vc(e)c(u)+∑e∋uc(e)≠c(v)+∑e∋vc(e). The least kk guaranteeing the existence of such a colouring is denoted χ″∑(G)χ″∑(G). We investigate a daring conjecture presuming that χ″∑(G)≤Δ(G)+3χ″∑(G)≤Δ(G)+3 for every graph GG, a seemingly demanding problem if confronted with up-to-date progress in research on the Total Colouring Conjecture itself.We note that χ″∑(G)≤Δ(G)+2col(G)−1 and apply Combinatorial Nullstellensatz to prove a stronger bound: χ″∑(G)≤Δ(G)+⌈53col(G)⌉. This imply an upper bound of the form χ″∑(G)≤Δ(G)+constχ″∑(G)≤Δ(G)+const. for many classes of graphs with unbounded maximum degree. In particular we obtain χ″∑(G)≤Δ(G)+10χ″∑(G)≤Δ(G)+10 for planar graphs.In fact we show that identical bounds also hold if we use any set of kk real numbers instead of {1,2,…,k}{1,2,…,k} as edge colours, and moreover the same is true in list versions of the both concepts.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 202, 31 March 2016, Pages 163–173
نویسندگان
,