Pkn的均匀全染色

设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.并称χeT(G)=min{k|G存在k-均匀全染色}为G的均匀全染色数.本文将通过很好的全染色方法得到χeT(Pkn)=5(n≥2k 1),并证明了对Pkn,[5]中猜想是正确的.     

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]中猜想是正确的.     

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

本文证明了,如果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的点边列表全色数。     

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

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

一类新的排序不等式

以微分中值定理为工具,建立了一类新的排序不等式,而经典的排序不等式仅是它的一个简单特例.     

小度数图的邻点可区别全染色

本文研究了最大度为3且没有相邻最大度的图的邻点可区别全染色.利用边剖分的方法,构造了此类图更为一般的情形,得到了它们的邻点可区别全色数的上界.目前,未找到最大度为3的图且它的邻点可区别全色数是6.本文的结果部分地回答了这个问题.     

小度数图的邻点可区别全染色

本文研究了最大度为3 且没有相邻最大度的图的邻点可区别全染色. 利用边剖分的方法, 构造了此类图更为一般的情形, 得到了它们的邻点可区别全色数的上界. 目前, 未找到最大度为3 的图且它的邻点可区别全色数是6. 本文的结果部分地回答了这个问题.     

图全染色的几个定理

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

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

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

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

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

Halin-图的点强全染色

图G(V,E)的一个k-正常全染色f叫做一个k-点强全染色当且仅当对任意v∈V(G), N[v]中的元素被染不同色,其中N[v]={u|uv∈V(G)}∪{v}．χTvs(G)=min{k|存在图G的k- 点强全染色}叫做图G的点强全色数．对3-连通平面图G(V,E),如果删去面fo边界上的所有点后的图为一个树图,则G(V,E)叫做一个Halin-图．本文确定了最大度不小于6的Halin- 图和一些特殊图的的点强全色数XTvs(G),并提出了如下猜想:设G(V,E)为每一连通分支的阶不小于6的图,则χTvs(G)≤△(G) 2,其中△(G)为图G(V,E)的最大度．     

Coloring graphs which have equibipartite complements

If G is a graph of order $2n \geq 4$ with an equibipartite complement, then G is Class 1 (i.e., the chromatic index of G is Δ (G)) if and only if G is not the union of two disjoint K_n's with n odd. Similarly if G is a graph of order 2n ≥ 6 whose complement G is equibipartite with bipartition (A, D), and if both G and B, the induced bipartite subgraph of G with bipartition (A, D), have a 1-factor, then G is Type 1 (i.e., the total chromatic number of G is Δ (G) + 1). © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 183–194, 1997     

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

圈的关联图的一般邻点可区别染色指标

给出了圈的关联图的一般邻点可区别色指标和一般邻点可区别全染色指标.     

联图Fn∨Pm的邻点可区别全染色

设G(V,E)是阶数至少为2的简单连通图,k是正整数,V∪E到{1,2,3,…k}的映射f满足:对任意uv,uw∈E(G),u≠w,有f(uv)≠f(vw);对任意uv∈E(G),有f(u)≠f(v), f(u)≠f(uv),f(v)≠f(uv);那么称f为G的k-正常全染色,若f还满足对任意uv∈E(G),有G(u)≠C(v),其中C(u)={f(u)}∪{f(uv)|uv∈E(G),v∈V(G)}那么称f为G的k-邻点可区别的全染色(简记为k-AVDTC),称min{k|G有k-邻点可区别的全染色}为G的邻点可区别的全色数,记作Xat(G)．本文得到了联图Fn∨Pm的全色数．     

若干联图的均匀全染色

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

广义Mycielski图的邻强边色数和邻点可区别全色数的两个上界

对简单图G,|V(G)|=p,n是自然数,Mn(G)被称为图G的广义Mycielski图,如果V(Mn(G))={v01,v02,…,v0p;v11,v12,…,v1p;…;vn1,vn2,…,vnp},E(Mn(G))=E(G)∪{vijv(i+1)k|v0jv0k∈E(G),1≤j,k≤p,i=0,1,…,n-1}.文中针对简单图G与它的广义Mycielski图之间的关系,给出了G的广义Mycielski图的邻强边色数和邻点可区别全色数的两个上界.