关于图Pκn的均匀染色

对简单图G=〈V,E〉及自然数k,令V(Gk)=V(G),E(Gk)=E(G)U{uv|d(u,v)=k},其中d(u,v)表示G中u,v的距离,称图Gk为G的k方图.本文讨论了路的k方图Pkn的均匀点染色、均匀边染色和均匀邻强边染色,利用图的色数的基本性质和构造染色函数的方法,得到相应的色数Xev(Pkn),Xec(Pkn),Xeas(Pkn).并证明猜想"若图G有m-EASC,则一定有m+1-EASC"对Pkn是正确的.     

若干图的倍图的均匀邻强边染色

如果图G的一个正常边染色满足相邻点的色集不同,且任意两种颜色所染边数目相差不超过1,则称为均匀邻强边染色,其所用最少染色数称为均匀邻强边色数．本文得到了星、扇和轮的倍图的均匀邻强边色数．     

一些图的Mycielski图的均匀邻强边染色

如果图G的一个正常边染色满足相邻点的色集不同,且任意两种颜色所染边数目相差不超过1,则称为均匀邻强边染色,其所用最少染色数称为均匀邻强边色数.本文得到了路、圈、星和扇的Mycielski图的均匀邻强边色数.     

图 P2×Cn的均匀邻强边色数

对图G(V,E),一正常边染色f若满足(1)对(V)uv∈E(G),f[u]≠f[v],其中f[u]={f(uv)|uv∈E};(2)对任意i≠j,有||E|-|Ej||≤1,其中Ei={e| e∈E(G)且f(e)=i}.则称f为G(V,E)的一k-均匀邻强边染色,简称k-EASC,并且称Xcas(G)=min{k|存在G(V,E)的一k-EASC为G(V,E)的均匀邻强边色数.本文得到了图P2×Cn的均匀邻强边色数.     

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

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

P_n~k的均匀全染色

设G(V,E)是一个简单图,f是G的一个k-正常全染色,若f满足||Vi∪Ei|-|Vj∪Ej||≤1(i≠j),其中Vi∪Ei={v|f(v)=i}∪{e|f(e)=i},则称f为G的k-均匀全染色,简记为k-ETC.并称eχT(G)=min{k|G存在k-均匀全染色}为G的均匀全染色数.本文将通过很好的全染色方法得到eχT(Pkn)=5(n≥2k+1),并证明了对Pkn,[5]中猜想是正确的.     

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

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

完全图的广义Mycielski图的邻强边染色

对|V(G)|≥3的连通图G,若κ-正常边染色法满足相邻点的色集合不相同,则称该染色法为κ-邻强边染色,其最小的κ称为图G的邻强边色数。张忠辅等学者猜想:对|V(G)|≥3的连通图G,G≠C_5其邻强边色数至多为△(G)+2,利用组合分析的方法给出了完全图的广义Mycielski图的邻强边色数,从而验证了图的邻强边染色猜想对于此类图成立。     

正则图的邻强边染色和全染色

如果~$k$-\-正则图~$G$~不含~5-\-圈的分支, 则猜测~$\chi''_{\mathrm{as}}(G) = \chi_{\mathrm t}(G)$. 证明这个猜想对很多图类都成立, 例如: 第1类型图、 $2$-\-正则图、$3$-\-正则图、$(|V(G)|-2)$-\-正则图、二部图、完全等多部图、$k$-\-方体以及一些特殊的联图类等.     

若干联图的均匀全染色

图$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$ 的均匀全色数.     

最大度不小于5的外平面图的邻强边染色

图G(V,E)的一k-正常边染色叫做k-邻强边染色当且仅当对任意uv∈E(G)有,f[u]≠f[v],其中f[u]={f(uw)|uw∈E(G)},f(uw)表示边uw的染色.并且x'as(G)=min{k|存在k-图G的邻强边染色}叫做图G的图的邻强边色数.本文证明了对最大度不小于5的外平面图有△≤x'as(G)≤△ 1,且x'as(G)=△ 1当且仅当存在相邻的最大度点.     

1-树图的邻强边染色

图G的一k-正常边染色f若使得任意uv∈E(G)满足f[u]≠f[v],其中f[u]={f(uω)|uw∈E(G)},则称f为G的一k-邻强边染色,简称k-ASEC,并称χ_as(G)=min{k|存在G的一k-ASEC}为G的邻强边色数.本文提出了邻强边染色猜想:对2-连通图G(V,E)(G(V,E)≠C₅),有△(G)≤χ_as(G)≤△(G)+2,并研究了1-树图的邻强边染色,证明了对△(G)≥4的1-树图G有△(G)≤χ_as<     

Halin-图的邻强边染色

图G(V,E)的正常κ-边染色f叫做图G(V,E)的κ-邻强边染色当且仅当任意uv∈E(G)满足f[u]≠f[v],其中,f[u]={f(uw)|uw∈E(G)},称f是G的κ-临强边染色,简记为κ-ASEC.并且x′_as(G)=min{k|κ-ASEC of G}叫做G(V,E)的邻强边色数.本文研究了△(G)≥5的Halin-图的邻强边色数.     

路与圈图的联图的均匀强边染色

For a proper edge coloring c of a graph G,if the sets of colors of adjacent vertices are distinct,the edge coloring c is called an adjacent strong edge coloring of G.Let c i be the number of edges colored by i.If |c i c j | ≤ 1 for any two colors i and j,then c is an equitable edge coloring of G.The coloring c is an equitable adjacent strong edge coloring of G if it is both adjacent strong edge coloring and equitable edge coloring.The least number of colors of such a coloring c is called the equitable adjacent strong chromatic index of G.In this paper,we determine the equitable adjacent strong chromatic index of the joins of paths and cycles.Precisely,we show that the equitable adjacent strong chromatic index of the joins of paths and cycles is equal to the maximum degree plus one or two.     

图的Smarandachely邻点边色数的界

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