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

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

图的一般邻点可区别均匀边染色和均匀全染色

提出了一般邻点可区别均匀边染色和全染色的新概念,研究了路P_n、圈C_n、星S_n、扇F_n、轮W_n、完全二部图K_(m,n)、2维平面网格图P_m×P_n的一般邻点可区别均匀边染色和全染色,具体给出这些图的一般邻点可区别均匀边染色和全染色指标.     

P_m∨C_n及C_m∨C_n的点可区别全染色

为了找到联图P_m∨C_n及C_m∨C_n的点可区别全染色利用其组合度用构造法得到了P_m∨C_n及C_m∨C_n的点可区别全染色方法并得到了其点可区别全色数(m≠n).     

M(C_n)和M(W_n)图的邻点可区别的Ⅰ-全色数

研究了M(C_n)和M(W_n)图的邻点可区别的I-一全染色.根据M(C_n)和M(W_n)图的构造特征,利用构造函数法,构造了一个从点边集V(G)∪E(G)到色集合{1,2,…,k)的函数,给出了一种染色方案,得到了它们的邻点可区别的I-全色数.     

冠图Cm·Cn与Cm·Kn的邻点可区别I-全染色

为了寻找一般图的邻点可区别I-全染色法,应用构染色函数法给出了冠图Cm·Cn和Cm·Kn的邻点可区别I-全染色,得到了其邻点可区别I-全色数,进一步验证了邻点可区别I-全染色的猜想.     

棋盘图的几种染色

染色问题是图论的重要研究内容之一,采用一种全新的方法给出了一类特殊图——棋盘图的邻点可区别边染色和邻点可区别全染色,并给出了相应的色数.     

图的半强积的邻点可区别染色

两个简单图G与H的半强积G·H是具有顶点集V(G)×V(H)的简单图,其中两个顶点(u,v)与(u',v')相邻当且仅当u=u'且vv'∈E(H),或uu'∈E(G)且vv'∈E(H).图的邻点可区别边(全)染色是指相邻点具有不同色集的正常边(全)染色.统称图的邻点可区别边染色与邻点可区别全染色为图的邻点可区别染色.图G的邻点可区别染色所需的最少的颜色数称为邻点可区别染色数,并记为X_a~((r))(G),其中r=1,2,且X_a~((1))(G)与X_a~((2))(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}的函数,给出了一种染色方案,得到了它们的关联邻点可区别的全色数.     

关于图的一般邻点可区别全染色

提出了一般邻点可区别全染色的新概念,给出了路、圈、星、树、二部图、轮、扇、完全图的一般邻点可区别全染色指标.并据此提出猜想.     

若干倍图的邻点可区别Ⅵ-全染色

图的一个边正常的全染色满足相邻点的色集合不同时被称为邻点可区别Ⅵ-全染色,把所用的最少颜色数称为邻点可区别Ⅵ-全色数,其中任意一点的色集合为点上与关联边所染的颜色构成的集合.应用构造邻点可区别Ⅵ-全染色函数法得到了路、圈、星和扇的倍图的邻点可区别Ⅵ-全色数,进一步验证图的邻点可区别Ⅵ-全染色猜想.     

图P_m□K_n的邻点可区别Ⅰ-全染色

应用构造具体染色的方法给出了m阶路和n阶完全图K_n的Cartesian积图的令β点可区别I-全染色得到了图P_m囗K_n的邻点可区别I-全色数.     

联图的关联着色

图G的一个κ-关联着色是指从G的关联集I(G)到颜色集{1,2,…,κ}的一个映射,满足任意一对相邻的关联分配到不同的颜色.使得G有κ-关联着色的最小的数κ称为G的关联色数,记为X_i(G).研究了联图的关联着色,给出了G∨H的关联色数的一个上界,讨论了路与路,路与圈,圈与圈的联图的关联色数.     

C_m·F_n和C_m·Cn的邻点可区别VE-全色数

根据冠图C_m·F_n和C_m·C_n的结构性质,用穷染,递推的方法,讨论了两类冠图C_m·F_n和C_m·C_n的邻点可区别VE-全染色,得到了相应的色数,当m≥3,n≥3时,x′_(at)~(ve)(C_m·F_n)=4,x′_(at)~(ve)(C_m·C_n)=(?),并给出了一种染色方案.     

关于一类二部图的均匀邻点可区别全染色

若图的邻点可区别全染色的各色所染元素数之差不超过1,则称该染色法为图的均匀邻点可区别全染色,而所用的最少颜色数称为该图的均匀邻点可区别全色数.本文给出了一类二部图的均匀邻点可区别全染色数.     

K_(2s)×K_(2t)的邻点可区别全染色

基于完全图的邻点可区别全染色,得到了任意偶阶完全图的直积图K_(2s)×K_(2t)的邻点可区别全色数χ_(at)(K_(2s)×K_(2t)=2(s+t)(t、s均为正整数).     

On the adjacent vertex-distinguishing acyclic edge coloring of some graphs

A proper edge coloring of a graph G is called adjacent vertex-distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the coloring set of edges incident with u is not equal to the coloring set of edges incident with v, where uv ∈ E(G). The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by x′ _Aa (G), is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. If a graph G has an adjacent vertex distinguishing acyclic edge coloring, then G is called adjacent vertex distinguishing acyclic. In this paper, we obtain adjacent vertex-distinguishing acyclic edge coloring of some graphs and put forward some conjectures.