Neighbor Sum Distinguishing Index of Sparse Graphs

A proper k-edge coloring of a graph G is an assignment of one of k colors to each edge of G such that there are no two edges with the same color incident to a common vertex. Let f(v) denote the sum of colors of the edges incident to v. A k-neighbor sum distinguishing edge coloring of G is a proper k-edge coloring of G such that for each edge uv∈E(G), f(u)≠f(v). By χ'_∑(G), we denote the smallest value k in such a coloring of G. Let mad(G) denote the maximum average degree of a graph G. In this paper, we prove that every normal graph with mad(G) ■ and Δ(G) ≥ 8 admits a(Δ(G) + 2)-neighbor sum distinguishing edge coloring. Our approach is based on the Combinatorial Nullstellensatz and discharging method.     

Neighbor Sum Distinguishing Total Choice Number of Planar Graphs without 6-cycles

Pil?niak and Wo?niak put forward the concept of neighbor sum distinguishing (NSD) total coloring and conjectured that any graph with maximum degree Δ admits an NSD total (Δ+3)-coloring in 2015. In 2016, Qu et al. showed that the list version of the conjecture holds for any planar graph with Δ ≥ 13. In this paper, we prove that any planar graph with Δ ≥ 7 but without 6-cycles satisfies the list version of the conjecture.     

Neighbor sum distinguishing total colorings of triangle free planar graphs

A total k-coloring c of a graph G is a proper total coloring c of G using colors of the set[k] = {1, 2,..., k}. Let f(u) denote the sum of the color on a vertex u and colors on all the edges incident to u. A k-neighbor sum distinguishing total coloring of G is a total k-coloring of G such that for each edge uv ∈ E(G), f(u) = f(v). By χ nsd(G), we denote the smallest value k in such a coloring of G. Pil′sniak and Wo′zniak conjectured that χ nsd(G) ≤Δ(G) + 3 for any simple graph with maximum degree Δ(G). In this paper, by using the famous Combinatorial Nullstellensatz, we prove that the conjecture holds for any triangle free planar graph with maximum degree at least 7.     

若干联图的邻点可区别-点边全染色

设G(V,E)是简单图,k是正整数.从V(G)∪E(G)到{1,2,…,k}的映射f被称作G的邻点可区别-点边全染色,当且仅当:■uv∈E(G),f(u)≠f(uv),f(v)≠f(uv),■uv∈E(G),C(u)≠C(v),且称最小的数k为G的邻点可区别-点边全色数.其中C(u)={f(u)}∪{f(uv)|uv∈E(G)},研究了一些联图的邻点可区别-点边全染色法,得到了它们的色数.     

Neighbor sum distinguishing total colorings via the Combinatorial Nullstellensatz

Let G=(V,E)be a graph andφbe a total coloring of G by using the color set{1,2,...,k}.Let f(v)denote the sum of the color of the vertex v and the colors of all incident edges of v.We say thatφis neighbor sum distinguishing if for each edge uv∈E(G),f(u)=f(v).The smallest number k is called the neighbor sum distinguishing total chromatic number,denoted byχ′′nsd(G).Pil′sniak and Wo′zniak conjectured that for any graph G with at least two vertices,χ′′nsd(G)(G)+3.In this paper,by using the famous Combinatorial Nullstellensatz,we show thatχ′′nsd(G)2(G)+col(G)-1,where col(G)is the coloring number of G.Moreover,we prove this assertion in its list version.     

树的Mycielski图的邻点可区别全色染色

A k-proper total coloring of G is called adjacent distinguishing if for any two adjacent vertices have different color sets.According to the property of trees,the adjacent vertex distinguishing total chromatic number will be determined for the Mycielski graphs of trees using the method of induction.     

一些分裂图的点可区别全染色

图G的一个k-正常染色被称为点可区别全染色指任意两点的点及其关联边所染色集合不同.研究了一些分裂图K_(2n+1)\E(K_m)(n≥4,m≥3)的点可区别全色数.     

图的邻点可区别全染色的渐近性质

图G的一个正常全染色被称为邻点可区别全染色,如果G中任意两个相邻点的色集合不同,其所用的最少颜色数称为邻点可区别全色数.张忠辅老师猜想:对于|V(G)|≥3的连通图G,其邻点可区别全色数最多不超过△(G)+3.用概率方法证明了对简单图G,△≥14,有χ_(at)(G)≤△+C,其中C≥10~(26)+1.     

广义Peterson图的邻点可区别的全染色

设P_(n,k)是一个简单图,其顶点集和边集分别为:V(P_(n,k))={u_0,u_1,…u_(n-1),v_0,v_1,…v_(n-1)},E(P_(n,k))={u_iu_(i+1),u_iv_i,v_iv_(1+k)},则称P_(n,k)为广义Peterson图,其中n≥5,0相似文献   

Neighbor Distinguishing Edge Colorings Via the Combinatorial Nullstellensatz Revisited

Consider a simple graph and its proper edge coloring c with the elements of the set . We say that c is neighbor set distinguishing (or adjacent strong) if for every edge , the set of colors incident with u is distinct from the set of colors incident with v. Let us then consider a stronger requirement and suppose we wish to distinguishing adjacent vertices by sums of their incident colors. In both problems the challenging conjectures presume that such colorings exist for any graph G containing no isolated edges if only . We prove that in both problems is sufficient. The proof is based on the Combinatorial Nullstellensatz, applied in the “sum environment.” In fact the identical bound also holds if we use any set of k real numbers instead of as edge colors, and the same is true in list versions of the both concepts. In particular, we therefore obtain that lists of length ( in fact) are sufficient for planar graphs.     

外平面图的全染色与列表全染色

本文证明了,如果G是满足条件Δ(G)≥4的外平面图,则x_T~L(G)=Δ(G) 1,同时对Δ(G)=3给出了XT(G)=Δ(G) 1的简短的新证明,从而蕴含Δ(G)≥3时,XT(G)=Δ(G) 1,其中XT(G)是G的点边全色数,x_T~L(G)是G的点边列表全色数。     

On the Neighbor Sum Distinguishing Index of Planar Graphs

Let c be a proper edge coloring of a graph with integers . Then , while Vizing's theorem guarantees that we can take . On the course of investigating irregularities in graphs, it has been conjectured that with only slightly larger k, that is, , we could enforce an additional strong feature of c, namely that it attributes distinct sums of incident colors to adjacent vertices in G if only this graph has no isolated edges and is not isomorphic to C₅. We prove the conjecture is valid for planar graphs of sufficiently large maximum degree. In fact an even stronger statement holds, as the necessary number of colors stemming from the result of Vizing is proved to be sufficient for this family of graphs. Specifically, our main result states that every planar graph G of maximum degree at least 28, which contains no isolated edges admits a proper edge coloring such that for every edge of G.     

图全染色的几个定理

图的全染色是染色理论的重要内容 ,全染色猜想 :设 G是一个简单图 ,则 XT( G)≤△ ( G) +2是一个至今未解决的问题 .本文证明了对于一些图类全染色猜想是正确的 .     

List neighbor sum distinguishing edge coloring of subcubic graphs

A proper $k$-edge-coloring of a graph with colors in $\{1,2,\dots ,k\}$ is neighbor sum distinguishing (or, NSD for short) if for any two adjacent vertices, the sums of the colors of the edges incident with each of them are distinct. Flandrin et al. conjectured that every connected graph with at least $6$ vertices has an NSD edge coloring with at most $\Delta +2$ colors. Huo et al. proved that every subcubic graph without isolated edges has an NSD $6$-edge-coloring. In this paper, we first prove a structural result about subcubic graphs by applying the decomposition theorem of Trotignon and Vu?kovi?, and then applying this structural result and the Combinatorial Nullstellensatz, we extend the NSD $6$-edge-coloring result to its list version and show that every subcubic graph without isolated edges has a list NSD $6$-edge-coloring.     

完全二部图K_(1,n),K_(2,n)和K_(3,n)的点强可区别全染色

设f是图G的一个正常全染色.对任意x∈V(G),令C(x)表示与点x相关联或相邻的元素的颜色以及点x的颜色所构成的集合.若对任意u,v∈V(G),u≠v,有C(u)≠C(v),则称.f是图G的一个点强可区别全染色,对一个图G进行点强可区别全染色所需的最少的颜色的数目称为G的点强可区别全色数,记为X_(vst)(G).讨论了完全二部图K_(1,n),K_(2,n)和L_(3,n)的点强可区别全色数,利用组合分析法,得到了当n≥3时,X_(vst)(K_(1,n)=n+1,当n≥4时,X_(vst)(K_(2,n)=n+2,当n≥5时,X_(vst)(K_(3,n))=n+2.     

若干联图的均匀全染色

图$G(V,E)$的全色数 $\chi_{t}(G)$就是将$V\bigcup E$分成彼此不相交的全独立分割集的最小个数。 如果任何两个$V\bigcup E$的全独立分割集的元素数目相差不超过1，那么 $V \bigcup E$的全独立分割集的最小个数就称为图$G$的均匀全色数，记为$\chi_{et}(G)$。 在本文中我们给出了当 $m \geq n \geq 3$ 时 $W_m\bigvee K_n$，$F_m \bigvee K_n$及$S_m \bigvee K_n$ 的均匀全色数.     

Neighbor sum distinguishing edge coloring of subcubic graphs

A proper edge-k-coloring of a graph G is a mapping from E(G) to {1, 2,..., k} such that no two adjacent edges receive the same color. A proper edge-k-coloring of G is called neighbor sum distinguishing if for each edge uv ∈ E(G), the sum of colors taken on the edges incident to u is different from the sum of colors taken on the edges incident to v. Let χ_Σ'(G) denote the smallest value k in such a coloring of G. This parameter makes sense for graphs containing no isolated edges(we call such graphs normal). The maximum average degree mad(G) of G is the maximum of the average degrees of its non-empty subgraphs. In this paper, we prove that if G is a normal subcubic graph with mad(G) 5/2,then χ_Σ'(G) ≤ 5. We also prove that if G is a normal subcubic graph with at least two 2-vertices, 6 colors are enough for a neighbor sum distinguishing edge coloring of G, which holds for the list version as well.     

一类4-正则平面图的邻点可区别关联色数

所谓图R_n是指具有如下结构的平面图:R_n=(V,E),其中顶点集合V={u_1,u_2,…,u_n}U{v_1,v_2,…,v_n},边集合E={u_iu_(i+1),v_iv_(i+1),u_iv_i,u_iv_(i+1)|i=1,2,…,n},其中u_(n+1)=u_1,v_(n+1)=v_1.通过研究R_n的邻点可区别关联着色,给出了当n=4,n是3或者5的正整数倍时,R_n的邻点可区别关联色数.