一些图的邻点可区别关联着色

在图的关联着色概念的基础上定义了图的邻点可区别关联着色及邻点可区别关联色数,研究了圈、完全二部图、Cm.Fn图的邻点可区别关联着色,并确定了它们的邻点可区别关联色数.     

围长至少为4的平面图的邻点可区别边色数

图G的邻点可区别边染色是G的正常边染色,使得每一对相邻顶点有不同的颜色集合．G的邻点可区别边色数X＇a（G）是使得G有一个k-邻点可区别边染色的最小正整数七．本文证明了：若G是围长至少为4且最大度至少为6的平面图,则X＇a（G）≤△＋2．     

图的邻点可区别Ⅵ-全色数和邻点可区别E-全色数

利用穷染、递推的方法讨论了路、圈、完全图、轮和扇的邻点可区别Ⅵ-全染色.并用概率方法研究了一般图的邻点可区别E-全染色,给出了图的邻点可区别E-全色数的一个上界.即δ≥7且△≥28,则有x_(at)~e(G)≤10△,其中δ是图G的最小度,△是图G的最大度.     

圈的广义冠图的关联邻点可区别的全色数

研究了圈的广义冠图C_noC_m,C_n oF_m和C_no W_m的关联邻点可区别的全染色.根据圈的广义冠图C_noC_m,C_noF_m和C_noW_m的构造特征,利用构造函数法,构造了一个从集合V(G)∪E(G)到色集合{1,2,…,k}的函数,给出了一种染色方案,得到了它们的关联邻点可区别的全色数.     

Pm□Pn的Smarandachely-邻点可区别边色数

图G的正常边染色f满足相邻点的色集合相不互包含时,该染色称为图G的Smarandcchely-邻点可区别边染色,其中S(x)={f(xw)|xw∈E(G)}称之为在f下的顶点x的色集合.该染色称为图G的Smarandchely-邻点可区别边染色.对图G进行的.Smarandchely-邻点可区别边染色所用最少颜色数称为图G的Smarandachely-邻点可区别边色数.讨论了Pm□Pn的Smarandchely-邻点可区别边色数.     

平面图的严格邻点可区别染色

图G的严格邻点可区别边染色是一个正常边染色,使得每对相邻顶点所关联的边的颜色集合互不包含.G的严格邻点可区别边色数χ’snd(G)是使G有一个严格邻点可区别k-边染色的最小整数k.本领域存在一个重要猜想:除去一个特殊图H_Δ外,每个没有叶子的简单图G都满足χ’snd(G)≤2Δ.当前最好的已知上界是χ’snd(G)≤3Δ-1.一个自然而有趣的问题是,哪类没有叶子的图满足χ’snd(G)≤Δ+C,其中C是一个不依赖于最大度Δ的常数?本文部分地回答了这个问题,即证明了对围长至少为5的平面图G,有χ’snd(G)≤Δ+25.这里围长大于等于5的条件不能被减弱到小于等于4的情形.     

高度平面图的邻点可区别全染色

图G 的邻点可区别全染色是G 的一个正常全染色, 使得每一对相邻顶点有不同的颜色集合. G的邻点可区别全色数χ_a′′ (G) 是使得G 有一个k- 邻点可区别全染色的最小颜色数k. 本文证明了: 若G 是满足最大度Δ(G) ≥ 11 的平面图, 则χ_a′′ (G) ≤ Δ(G) + 3.     

Δ(G)=5的2-连通外平面图的邻点可区别全染色

Smarandachely邻点可区别全染色是指相邻点的色集合互不包含的邻点可区别全染色,是对邻点可区别全染色条件的进一步加强。本文研究了平面图的Smarandachely邻点可区别全染色,即根据2-连通外平面图的结构特点,利用分析法、数学归纳法,刻画了最大度为5的2-连通外平面图的Smarandachely邻点可区别全色数。证明了：如果$G$是一个$Delta （G）=5$的2-连通外平面图,则$chi_{rm sat}（G）leqslant 9$。     

扇的倍图的邻点可区别边色数

设G(V,E)是阶数至少是3的简单连通图,若f是图G的k-正常边染色,使得对任意的uv∈E(G),C(u)≠C(v),那么称f是图G的k-邻点可区别边染色(k-ASEC),其中C(u)={f(uw)│uw∈E(G)},而χa′s(G)=min{k│存在G的一个k-ASEC},称为G的邻点可区别边色数.本文给出扇的倍图D(Fm)的邻点可区别边色数.     

若干笛卡尔积图的邻点可区别关联染色

An adjacent vertex distinguishing incidence coloring of graph G is an incidence coloring of G such that no pair of adjacent vertices meets the same set of colors.We obtain the adjacent vertex distinguishing incidence chromatic number of the Cartesian product of a path and a path,a path and a wheel,a path and a fan,and a path and a star.     

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

设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)},研究了一些联图的邻点可区别-点边全染色法,得到了它们的色数.     

若干星的冠图的邻点可区别V-全染色

根据星与圈(星、扇、轮、路)构造的冠图的结构性质,应用分析和构造函数法研究了邻点可区别V-全染色,得到了S_n·C_m,S_n·S_m,S_n·F_m,S_n·W_m,S_n·P_m的邻点可区别V-全色数.     

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

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

树的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.     

广义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相似文献   

图的Smarandachely邻点边色数的界

对图G的一个k-正常变染色法f,若图G中任意相邻两点的相邻边色集合互相不包含,那么称f为图G的一个k-Smarandachely邻点边染色(简记为k-SEC),而最小的正整数k称为图G的Smarandachely邻点边色数.尝试应用Lovasz局部引理来得到了Smarandachely邻点边色数的上界.     

若干Mycielski图的邻点可区别E-全染色

设G(V,E)是简单连通图,k是正整数,若V∪到{1,2,3,…,k}的映射f满足对任意uv∈E(G),有f(U)≠f(v),f(u)≠f(uv)f(v)≠f(uv),且C(u)≠C(v),其中C(u):{f(u)}∪{f(uv)|uv∈E(G)}.那么称f为G的k-邻点可区别的E-全染色(简记为k-AVDETC),并称X_(at)~e(G)=min{k|G有k-邻点可区别的E-全染色}为G的邻点可区别的E-全色数.本文讨论了路、圈、扇、星、轮及完全图的Mycielski图的邻点可区别E-全染色,得到了该类图的邻点可区别的E-全色数.     

关于联图K_(2,n)∨P_m的邻点可区别的全染色

一个全染色被称为邻点可区别的如果它满足对任意两个相邻点所关联的色集合不同.本文给出了联图K2,n∨Pm的邻点可区别的全色数并且证明了它满足邻点可区别的全染色猜想.