积图P2×C6的邻点可区别全染色

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

混合Ramsey数X_2(m,k_(1,n))的下界

一个图G的全色数x_2(G)是着色G的边和顶点使相邻、关联元素均着不同色所需要的最少颜色数。对于正整数m和星形图K_(1,n),混合Ramsey数x_2(m,K_(1,n))是这样的最小正整数P,使得任一P阶图G或者有x_2(G)≥m,或者G的补图G含K_(1,n)为子图。本文引进全着色矩阵的概念,据此得到混合Ramsey数x_2(m,K_(1,n))的下界:对于m≥3、n≥1,有 x_2(m,K_(1,n))≥m+n-2。 结合Fink给出的上界可知,当m奇数、n偶数时,x_2(m,K_(1,n))=m+n-2;其余情况时,m+n-2≤x_2(m,K_(1,n))≤m+n-1。     

积图P_2×C_6的邻点可区别全染色

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

路和圈的弱直积图的星边色数

若图G的一个正常染色使得G中没有长为4的路是2-边染色的,则称此染色是G的一个星边染色,使得图G有星边染色的最小颜色数为星边色数,记作x′s(G).文章给出了路和圈的弱直积图的星边色数:对于图Pm×Cn(m≥2,n≥3)的星边色数分以下三种情形:x′s(P2×Cn)=3(n≥3);5≤x′s(Pm×Cn)≤6(m=3,4;n≥3);6≤x′s(Pm×Cn)≤8(m≥5,n≥3).     

非H-无爪图最长圈的若干性质

设G是2-连通无爪图,C是G的最长圈,R=G-C非空.证明了C满足以下5个性质;1)不存在c∈Nc(R),使G[N(c)]连通;2)不存在c∈Nc(R)和y∈V(G)(y≠c),使G[N(c)U{y}]连通且|N(y)∩N(c)|≥3;3)不存在c∈Nc(R)和y∈V(G),使G[N(c)∪{y}连通且G[N(y)]连通;4)不存在c∈Nc(R)和y∈K_1,使|N(y)∩(N(K_2)-{c}|≥2(其中K_1是G[N(c)]的含c~+,c~-的一个分支,K_2是另一个分支);5)不存在c∈Nc(R)和y∈V(G),使|N(y)∩K_1|≥2且有连接K_2与y的路P满足:对P的任一中途点u,或u∈V(C)或u~+u~-∈E(G).     

一类Halin-图的均匀色数

对Δ(G) =4的Halin -图证明了 |V(G) | 0 (mod3)时 ,对任意整数的k≥「Δ(G) / 2 +1,G是可均匀k -可着色的。从而证明了这类Halin -图的均匀染色数的下界是「Δ(G) / 2 +1。     

一类团横贯数等于团独立数的图

把图G的每一个团看作一个点，两点之间有边相连当且仅当它们对应的团有非空交（即有公共点）．这样得到的图称为图G的团图，记为K（G）．文章证明了如果一个图对应的团图为二部图，则该图的团横贯数等于团独立数，即τc（G）=ac（G），另外给出了判断一个图的团图是否为二部图的一个计算时间为o（n^4）的多项式时间算法．     

3-连通无爪图中的最长圈

证明了3-连通无爪图G中的最长圈C满足:|V(C)|≥min{3δ(G)+6,5δ(G)-5,4δ(G),|V(G)|}.     

关于图的3—色数

对 Harary 在文献[1]中的 n一色数的 n=3,进行了讨论,得到了 X_3(G),不可改进的上下界以及常见特殊图簇的 x_3(G),并得到了 X_3(G)与 X_3(?)、 X_3(G)与 X(?)不可改进的关系。     

2类非连通图的优美性

本文利用构造法,研究了2类非连通图图m·C3∪Gm-1及m·(P2∨K2—)∪Gm-1的优美性.证明了下面的结论:设m为任意的正整数,Gm-1是表示边数为m-1的优美图,则当m≥2时,图m·C3∪Gm-1及m·(P2∨K2—)∪Gm-1都是优美图.其中,C3是表示三个顶点的回路图,P2∨K2—是两个顶点的路P2与两个孤立顶点的图K2—的联图,m·C3是m个图C3恰有一个公共点的图,m·(P2∨K2—)是m个图P2∨K2—恰有一个公共点的图,G∪Gm-1是把图G与Gm-1不相交并起来所得的非连通图.     

单圈图和双圈图的群色数

若图G=(V,E),给定方向为D,A表示一个非平凡的阿贝尔群,F(G,A)表示映射f:E(G)→A的集合。若对任意f∈F(G,A)存在映射c:V(G)→A,使得G中的每一条有向边e=uυ∈E(G)(方向是u→υ)满足c(u)-c(v)≠f(e),这时说图G是A-可染的。使得图G在方向D下是A-可染的,A的最小阶数为图G的群色数,记为χg(G)。在分析单圈图和双圈图特性的基础上,讨论了它们的群色数。对于单圈图、双圈图可得出其群色数都是3。     

关于全着色Ramsey数

以 X_2(G)记一图 G 之全色数,全着色 Ramsey 数 X_2(m,n)为最小正整数 p,使得每一p 阶图 G 或有X_2(G)≥in加,或其补图■满足 X_2(■)≥n。本文给出 X_2(m,n)的上、下界。     

邻集交和汉密尔顿连通性

设G是阶为u(≥3),独立数为α的简单图,本文证明了:如果对于G中不相邻点u,υ都有|N(u)∩N(υ)|≥α,则G是汉密尔顿连通的,除非G同构于一类特殊图.     

全色数与小阶路的混合Ramsey数

以 X_2(G)记一图 G 之全色数,P_n 表 n 阶路,混合 Ramsey 数 X_2(m,P_n)为最小正整数 p.对于每个 p 阶图 G,或者 X_2(G)≥m,或者P_n 当 m 取任意正整数、n≤4时,本文得到 X_2(m,P_n)的确值。     

几族全着色临界图

本文引进全着色矩阵的概念,每个全着色矩阵确定一个简单图及其一全着色。若图G的全色数为k,G的任一真子图的全色数均小于k,称G为k-全着色临界图。对任意奇数r>3,我们给出若干阶数最小的非平凡r~-全着色临界图。     

关于C_3的St(n+1)冠的优美性

对于自然数n∈N(N为自然数集合),本文给出C3的St(n+1)冠,论证了该图是优美图,由此推 广了文献[4]的一些结果。     

F～K（m1，m2，m3）-S的必要条件

用P(G,λ)表示图G的色多项式。本文得到了图F与K(m1,m2,m3)-S色等价的必要条件,为我们进一步研究形如K(m1,m2,m3)-S的色唯一图提供了基础。     

特殊3-正则图的符号控制函数

对于顶点数为n的3-正则图G,当(A)v∈V(G),N(N[v])≤t时,则有G的上符号控制函数Γs(G)≤(t+2)/(t+4)n (0≤t≤6).     

正则k-覆盖图

图G的k-正则生成子图称为G的一个k-因子,若图G的每条边都含于G的一个k-因子中,称图G足k-覆盖的。对任意给定的正整数γ、λ和k(λ≥2),基于文[1,2]的已知结论,本文给出了所有γ-正则λ-边连通图是k-覆盖图的充分必要条件。     

关于x_4~T(G)+x_4~T(■)的可达下界问题

解决了张忠辅等人提出的如下问题:确定x_4~T(G)+x_4~T(G)用的可达下界,其中x_4~T(G)表图G的4-全色数,G表G的补图。