Halin图的邻和可区别全染色

令[k]={1,2,…,k},Φ为图G的一个正常[k]-全染色。用f(v)表示点v及所有与其关联的边的颜色的加和,如果对任意边uv∈E(G),有f(u)≠f(v),则称该染色为图G的[k]-邻和可区别全染色。k的最小值称为图G的邻和可区别全色数,记为χ″Σ(G)。Pils'niak和Woz'niak提出猜想:对任意简单图G,有χ″Σ(G)≤Δ(G)+3,其中Δ(G)表示图G的最大度。运用组合零点定理证明了该猜想对于任一Halin图成立。     

立方图的邻点可区别全染色及一般邻点可区别全染色

根据圈的立方图的性质,利用穷染、置换的方法,研究了立方图C3n的邻点可区别全染色及一般邻点可区别全染色.通过设计染色方案,给出了立方图C3n的邻点可区别全色数及一般邻点可区别全色数指标,且色数均可取到下界.     

中间图的邻点可区别全染色

设G是简单连通图,G的k-正常全染色f称为是邻点可区别的,如果对G的任意相邻的两顶点,其点的颜色及关联边的颜色构成的集合不同,称f为G的k-邻点可区别全染色,这样的k中最小者称为G的邻点可区别全色数,本文考虑了图的中间图的邻点可区别全色数,并确定了路、圈、星图和扇图的中间图的邻点可区别全色数.     

图的邻点可区别全染色算法

在图 G 的一个正常全染色下,G 中任意一点 v 的色集合是指点 v 的色以及与 v 关联的全体边的色所构成的集合。图 G 的邻点可区别全染色就是图 G 的正常全染色且使相邻点的色集合不同,其所用最少颜色数称为图 G的邻点可区别全色数。设计了一种启发式的邻点可区别全染色算法,该算法根据邻点可区别全染色的约束规则,确定四个子目标函数和一个总目标函数,然后借助染色矩阵及色补集合逐步迭代交换,每次迭代交换后判断目标函数值,当目标函数值满足要求时染色成功。实验结果表明,该算法可以得到图的邻点可区别全色数,并且算法的时间复杂度不超过 O（n3）。     

几类图的邻点可区别的全染色

邻点可区别的全染色是在正常全染色的定义上,使得相邻顶点的色集不同。定义并探讨了推广后的两类双钻图以及两个轮的hajós sum的邻点可区别的全色数。     

蛛网图的邻点可区别的全染色

通过穷举法和组合分析法研究蛛网图的邻点可区别的全染色,结果表明蛛网图的邻点可区别的全色数是存在的.     

若干图的邻点可区别的I-全染色和邻点可区别的I-均匀全染色

图G的一个邻点可区别的I-均匀全染色是指对图G的一个邻点可区别的I-全染色f,若f还满足任意两个色类(点和边)的颜色个数最大相差为1.对图G进行邻点可区别的I-均匀全染色所用颜色的最小数量称为图G的邻点可区别I-均匀全色数.文章通过函数构造法,研究并确定了路、圈、星、扇和轮的平方图的邻点可区别I-均匀全色数,并验证了其满足猜想:iaet(G)≤Δ(G)+2.最后给出了C5∨Wn的邻点可区别I-全色数.     

多重Mycielski图的邻点可区别全染色

给出了一个简单图G的k重Mycielski图Mk（G）（其中k为正整数）的邻点可区别全色数的上界,得到了圈、星、轮、扇的k重Mycielski图的邻点可区别全色数.     

直积图的邻点可区别全染色

设G,H为简单图.给出直积图G×H的邻点可区别全色数的一个上界,得到星、轮、扇分别与m阶路、圈的直积图的邻点可区别全色数.     

蛛网图的邻点可区别V-全染色

研究了蛛网图的邻点可区别V-全染色.根据蛛网图的结构特点,利用穷染的方法,得到了蛛网图的邻点可区别V-全色数.进一步验证了图的邻点可区别V-全染色猜想.     

2-连通外平面图的邻点可区别全染色

运用数学归纳法及换色技巧,探讨了Δ(G)=7 的2-连通外平面图的邻点可区别全染色问题,使该问题在原有基础上得到了推广.     

Pm∨Pn的邻点可区别全染色

设G是阶数不小于2的简单连通图,G的k 正常全染色f称为是邻点可区别的,如果对G的任意相邻的两顶 点,其点的颜色及关联边的颜色构成的集合不同.这样的k中最小者称为是G的邻点可区别全色数.得到了两条路的 联图的邻点可区别全色数.     

路的广义Mycielski图的邻点可区别的全染色

图G的一个正常全染色称为G的邻点可区别的全染色,如果对于G中任意相邻的点u和v有C(u)≠C(v).研究图的邻点可区别的全染色就是找出图的邻点可区别全染色的最小色数.利用穷举法和组合分析法研究路的广义Mycielski图的邻点可区别的全染色,得到路的广义Mycielski图的邻点可区别的全色数.     

Halin图的一个点强全染色法

针对Halin图的点强全染色问题,提出一个有效的染色法———逐圈着色法,而且方法给出的方案也是最优的,即用最少的颜色完成Halin图的点强全染色.同时还确定了最大顶点度是3的Halin图的点强全色数的上下界,即上界为6,下界为5.     

几类笛卡尔积图的邻点可区别全染色

图G的邻点可区别全染色是指G的任意相邻顶点具有不同色集的全染色,所需要的最少颜色数称为G的邻点可区别全色数.文章得到了圈与星、轮、扇的笛卡尔积图的邻点可区别全色数.     

完全二部图K_(5,7)点强可区别全染色方案探讨

利用组合分析的方法先讨论了完全二部图K_(5,7)的点强可区别全染色,在此基础之上给出了两种具体的关于完全二部图K_(5,7)的点强可区别全染色方案.此结果的给出不仅确定了完全二部图K5,7的点强可区别全色数为9,而且对于胡志涛所提出的关于完全二部图的点强可区别全染色的猜想:"如果m≥4且n2 m-2时,那么χvst(Km,n)=n+3"中当m=5时作出了否定,从而进一步确定了此猜想成立的范围.     

无相交三角形平面图的邻点可区别边染色

图G的k-邻点可区别边染色是指G的一个正常k-边染色满足对任意相邻顶点u和v,与u关联的边所染颜色集合和与v关联的边所染颜色集合不同。使G有k-邻点可区别边染色的k的最小值称为G的邻点可区别边色数,记作χ'_a(G)。通过运用权转移方法研究了无相交三角形平面图的邻点可区别边色数,证明了若图G为无相交三角形平面图,则χ'_a(G)≤max{Δ(G)+2,10}。     

若干联图的邻点可区别关联染色

图G的邻点可区别关联染色是指G的任意相邻顶点具有不同色集的关联染色。研究了联图G∨Cm,G∨Sm和G∨Tm的邻点可区别关联染色,得到了相应的邻点可区别关联色数,其中G是n+1阶的星,轮或扇;Cm为m阶圈,Sm为m+1阶星,Tm为m阶树。