若干多重联图的邻点可区别E-全染色

G（V,E）是一个简单图,忌是一个正整数,f是一个V（G）∪E（G）到{1,2,…,k}的映射．如果任意uv∈E（G）,则f（u）≠f（v）,f（u）≠f（uv）,f（v）≠f（uv）,C（u）≠C（v）,称,是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数．本文给出了扇与星、路、圈间的多重联图的邻点可区别E-全色数．其中C（u）={f（u）}∪{f（uv）｜uv∈E（G）}．     

Cm·Kn的邻点可区别全染色

将顶点集和边集分别为V(G)={vij|i=1,2,…,m;i=0,1,…,n-1},E(G)={v10 v20,v20 v30,…,vm0 v10}∪(m∪i=1{vij vik|j≠k;j,k=0,1,…,n-1})的图简记为Cm·Kn.给出了图Cm·Kn的邻点可区别全色数.     

一类完全r-部图的邻点可区别全染色

一个正常的全染色满足相邻点的点染色及关联边的色集不同时，称为邻强全染色，其所用最少染色数称为邻强全色数(或邻点可区别的全色数)．给出了一类特殊的完全γ-部图邻点可区别的全色数．     

C23n,C24n邻点可区别的全染色

设G(V，E)是阶数不小于2的简单连通图，n是自然数，V∪E到{1，2，…，k}的映射f满足Vuv∈E(G)，f(u)≠f(v)，f(u)≠f(uv)≠f(v)；А↓uv,uw∈E(G),(v≠w)，f(uv)≠f(uw)；А↓uv∈E(G),G(u)≠C(v)．其中C(u)=f(u)∪{f(uv)|uv∈E(G)}．，f称为G(V,E)的一个邻点是可区分的全染色法，简记为k-AVDTC.其中最小的k称为G的邻点可区别的全色数。G^2是G再加上G中点间距离为2时连边后的图．本文得到了3n、4n阶圈C3n^2，C4n^2邻点可区别的全色数。     

若干图广义Mycielski图的点边邻点可区别的全染色

对简单图G(V,E),存在一个正整数k,使得映射f:V(G)∪E(G)→{1,2,…,k},如果对uv∈E(G),有f(u)≠f(uv),f(v)≠f(uv),且C(u)≠C(v),则称f是图G的点边邻点可区别全染色,且称最小的数k为图G的点边邻点可区别全色数.本文讨论了星,扇,轮,圈等图的广义Mycielski图的点边邻点可区别全染色,得到了它们的点边邻点可区别全色数,其中每个点的色集合包含该点及其关联边的颜色.     

K11-uv的邻点可区别全色数

一个正常的全染色满足相邻点的点染色及关联边的色集不同时，称为邻强全染色，其所用最少染色数称为邻强全色数(或点可区别的全色数)，证明了对u，υ∈V(K11)，则xat(K11-uυ)=13。     

两类笛卡尔积图的邻和可区别全染色

围绕邻和可区别全染色猜想,研究了路与路、圈与圈的笛卡尔积图的邻和可区别全染色,应用构造染色函数法,确定了它们的邻和可区别全色数,证明了邻和可区别全染色猜想对于两类笛卡尔积图成立,给该猜想提供了更有力的证据.     

联图Fs ∨ Km,n的邻点可区别全色数

设G是简单图,k是正整数,f是V(G)∪E(G)到{1,2,…,k}的映射.对任意u∈V(G),记C(u)={f(u)}U{f(uv)|uv∈E(G),v∈V(G)}.如果f为G的正常全染色,且对任意uv∈E(G),有C(u)≠C(v).那么称f为G的k-邻点可区别全染色(简记为k-AVDTC).称xat(G)=min{k|图G存在k-AVDTC}为G的邻点可区别全色数.给出了联图Fs ∨ Km,n的邻点可区别全色数.     

关于θ-图的邻点可区别全染色

u，v两点间连三条内部不相交的路且至多有一条长度为1的图，称为θ-图．设G是阶至少为2的连通图，k是正整数，f是V(G)∪E(G)到{1，2，3，…，k}的映射，对任意u∈V(G)，记C(u)={f(u)}∪{f(uv)|uv∈E(G)，v∈V(G)}．如果：1)对任意uv，vw∈E(G)u≠w，有f(uv)≠f(vw)；2)对任意uv∈E(G)，有f(u)≠f(v)，f(u)≠f(uv)，f(v)≠f(uv)；3)对任意uv∈E(G)，有C(u)≠C(v)，那么称f为G的k-邻点可区别全染色(简记为k-AVDTC)，称min{k|G有k-邻点可区别全染色}为G的邻最可区别全色数，记作Xat(G)．本文得到了θ-图的邻点可区别全染色。     

高度图的邻点可区别的全染色界的一点注

A.C.Burris猜想:对于一个简单图G,它的邻点可区别的全色数aχt(G)≤Δ(G) 3其中Δ(G)表示G的最大度,本文证明了对Δ(G)=|V(G)|-1时,猜想为真.     

关于图邻点可区别上界的一点注

设G为一简单连通图．它的一个正常全染色叫做一个邻点可区别的全染色．如果满足：对G的任意两个顶点u，v，都有染点u以及与u相连的边所形成的色集与染点v以及与v相连的边所形成的色集不同．如果一个邻点可区别的全染色需要的色数为k，则把这个染色叫做k—邻点可区别的全染色(简记为k—AVDTC)．对图G，记x′α(G)=min{k|G有一个k—AVDTC}，称x′α(G)为图G的邻点可区别的全色数．本文给出了邻点可区别的全色数的一个上界．     

扇和轮的倍图的点可区别均匀边染色

对于简单图G的正常边染色f,若对于u,v∈V(G),有C(u)≠C(v),称f是图G的点可区别边染色,(其中C(u)={f(uv)|uv∈E(G)}).若满足|Ei|-|Ej|≤1(i,j=1,2,…,k),(其中e∈Ei,f(e)=i(i=1,2,...,k)),则称f是图G的点可区别均匀边染色.本文讨论了扇和轮的倍图的点可区别均匀边染色.     

广义Mycielski图的邻点可约边染色

对简单图G(V,E),若存在自然数k(1≤k≤△(G))和映射f:E(G)→{1,2,…,k}使得对任意相邻两点u,(υ)V(G),u(υ)E( G),当d(u)=d(υ)时,有C(u)=C(υ),则f为G的k-邻点可约边染色,其所用最多染色数称为图G的邻点可约边色数,本文得到了若干广义Mycielski图的邻点可约边染色数.     

伪-Halin图的邻强边染色

对图G(V，E)，一正常k-边染色f称为图G(V，E)的k-邻强边染色，当且仅当任意uv∈E(G)，有f[u]≠f[u]，其中f[u]={f(uw)|uw∈E(G)}，并称x′。(G)=min{k|存在G的一k-ASEC}为G的邻强边色数．研究了△(G)≥5的伪-Halin图的邻强边色数，并通过归纳法证明了对△(G)=5的伪-Halin图G，有5≤x′as(G)≤6．如果E(G[V△])≠Ф，则,x′as(G)=6．并提出猜想：对|V(G)|≥6的连通图G(V，E)有△(G)≤x′as(G)≤△(G) 2．其中△(G)为G的最大度．     

关于图的局部着色

G.Chartand[1]引入了一个图G的局部色数x1(G)的概念,在本文中的我们主要出了图的局部色数的界限,证明了对任意n阶图G(n≥2),均有x1(G) x1(■)≤2n-1,并确下了一些特殊图的局部色数.     

联图PmVSn,n的邻点可区别全染色

简单连通图G(V,E)的κ-正常全染色f称为邻点可区别的,如果对G(V,E)的任意相邻两顶点,其顶点的颜色及关联边的颜色构成的集合不同.这样的κ中最小者称为G(V,E)的邻点可区别全色数.研究了路与双星图的联图PmV Sn,n邻点可区别的全染色问题,得到了联图PmV Sn,n邻点可区别的全色数.     

单圈图的邻强边染色

设G是阶数不小于3的简单连通图,G的k-正常边染色称为是邻强的,如果G的任意相邻的两顶点的关联边的颜色构成的集合不同.对一个图G进行邻强边染色所需要的最少的颜色数称为是G的邻强边色数.本文研究了单圈图的邻强边染色.