کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418521 681678 2016 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Neighbor sum distinguishing total choosability of planar graphs without 4-cycles
ترجمه فارسی عنوان
قابلیت انتخاب پذیری کامل مشخص کننده مجموع همسایگی گرافهای مسطح بدون چهار سیکل
کلمات کلیدی
رنگ آمیزی کل مشخص کننده مجموع همسایگی؛ قابلیت انتخاب پذیری؛ Combinatorial Nullstellensatz؛ نمودار مسطح
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Let G=(V,E)G=(V,E) be a graph and ϕϕ be a total kk-coloring of GG by using the color set {1,…,k}{1,…,k}. Let ∑ϕ(u)∑ϕ(u) denote the sum of the color of the vertex uu and the colors of all incident edges of uu. A kk-neighbor sum distinguishing total coloring of GG is a total kk-coloring of GG such that for each edge uv∈E(G)uv∈E(G), ∑ϕ(u)≠∑ϕ(v)∑ϕ(u)≠∑ϕ(v). By χΣ″(G), we denote the smallest value kk in such a coloring of GG. Pilśniak and Woźniak first introduced this coloring and conjectured that χΣ″(G)≤Δ(G)+3 for any simple graph GG. Let Lz(z∈V∪E)Lz(z∈V∪E) be a set of lists of integer numbers, each of size kk. The smallest kk for which for any specified collection of such lists, there exists a neighbor sum distinguishing total coloring using colors from LzLz for each z∈V∪Ez∈V∪E is called the neighbor sum distinguishing total choosability of GG, and denoted by chΣ″(G). In this paper, we prove that chΣ″(G)≤Δ(G)+3 for planar graphs without 4-cycles with Δ(G)≥7Δ(G)≥7. This implies that Pilśniak and Woźniak’ conjecture is true for planar graphs without 4-cycles.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 206, 19 June 2016, Pages 215–219
نویسندگان
, , ,