8—临界图边数的下界

本文给出了８－临界图边数的下界。     

关于9—临界图边数的下界

本文给出了9－临界图边数的下界：m≥118／39n,其中n为点九，m为边数。     

最大次数为3的色指数临界图的一种构造

G的k-(边)着色是一个映射π:E(G)→{1,2,…,k},使得G的相邻边没有相同的象.图G的色指数x'(G)=min{k| G有一个k-着色}.给出了最大次数为3的图的5种类型的四边形扩张变换,证明了这5种类型的变换保持图的临界性不变,并可利用这种变换构造出阶数较高的新的临界图.     

群色临界图的一些性质

群色数χ1(G)是最小数m,使得对任意Abel群A,若|A|≥m,则G是A-可着色的.称G是群色临界的,若对于G的任一真子图H,有χ1(H)<χ1(G).研究了群色临界图的一些性质,给出某些群色临界图的刻划,证明了k群色临界图G的最小度为k-1,且若G是3群色临界图当且仅当G是圈.     

边染色9-临界图边数的新下界

针对Vizirtg猜想△为9的情况，运用Discharging差值转移方法研究了9-临界图的边数下界，得到了新结论：m≥10^-36n,改进了已有结果。     

边染色7-临界图边数的新下界

运用差值转移规则研究了7-临界图的边数下界,改进了已有的结果。     

全着色边临界图的一个注记

研究了全着色边临界图的结构，证明了对于△≥5的全着色边临界图G（V，E），若u∈V（G），d（u）=3，uvi∈E（G）（i=1，2，3），则△-1≤d（vi）≤△．     

具有较小最大度的临界图边数的下界

运用Discharge法给出了不含2点和3点的6临界图及不含4点和5点的7临界图边数的下界．     

关于边着色临界图的一个问题

H.P.Yap在[1]中提出这样一个问题,是否存在偶阶边着色8临界图,它除了有一个2度点和两个3度点外其余的都是8度点?作为本文定理推论的一个特殊情形给出了这个问题的否定性答案。     

序图的边值和下界

引入图Ｇ的序图概念，给出一个图的所有序图边值和两个下界。     

边染色临界图边数的新下界

Vizing于1968年提出猜想:如果图G是一个点数为n,边数为m的Δ-临界图,那么满足m≥12[(Δ-1)n+3].根据临界图的若干引理,利用差值转移规则给出5-临界图和6-临界图(不含三圈)边数的新下界,改进了已有的结果.     

关于临界的圆色数的一个注记

圆色数是正常着色的一个推广,由Vince在1988年首次提出．现我们考虑这样一个问题：对于Vε〉0,是否存在一个具有高连通性的临界图G使得Xc（G）≤X（G）-1＋ε？对此,Steffen和Zhu已证明对Vm≥4存在满足要求的m-连通（m＋1）-临界图,只留下一种情形未解决,即G的连通度为3时的情形．在这篇文章中我们就此情形进行讨论,并给出肯定结论．     

关于3－控制临界图的某些结果

以γ（Ｇ）记图Ｇ的控制数，如果对ｖ（Ｇ）中任何一对满足条件ｕｖＥ（Ｇ）的顶点ｕ，ｖ，有γ（Ｇ＋ｕｖ）＜γ（Ｇ），则称Ｇ是控制临界的。γ（Ｇ）＝ｋ的控制临界图称为是ｋ－控制临界的，得出以下两个结果：１）如果Ｇ是具有以（＞＞２ｋ）个顶点的连通３－控制临界图，则Ｇ中度≤２ｋ的顶点的个数至多为２ｋ．２）每个连通３－控制临界图或者有一个独立３－控制集或者有一个完全３－控制集。     

图的星色数的两个结果

图G的星染色是图G的正常点染色,使得图G中没有长为3的路2-染色.通过应用概率方法中的非对称局部引理,证明了任一最大度为Δ的图的星色数χs(G)≤48Δ3.通过应用第一矩量原理和Markov不等式,证明了对任一有n个顶点的最大度为Δ的图G,其星色数χs(G)≤nΔ.     

二部图的3分划数及色惟一性的若干新结果

研究了当p≥q≥s 1≥10时,K-s(p,q)中图的3分划数的计算公式和3分划数一些下界及其极图,并得到了许多新的色惟一二部图.     

图的星边色数的一个新的上界

图的着色问题是图论中的一个重要问题,图论领域的诸多学者研究了图的各种着色.运用Lovsz局部引理,研究了图的星边着色(图G的星边着色是G的一个正常的边着色,并且使得G中无长为4的路是2-边着色的;图G的星边色数是G的所有星边着色中所使用的最小颜色数,记为χ’se(G)),并证明了最大度为Δ(Δ≥2)的简单无向图G的星边色数新的上界为χ’se(G)≤「9(Δ-1)3/2?.     

临界图性质的探讨

临界图是连通的第二类图,而且对于G的任意一条边e,G-e是第一类图。本文主要证明了满足一定条件的Δ=6的平面图不是临界的,并给出了临界图的一个性质.     

一类完全三部图的色等价图

我们已经得到了一些和完全三部图Km,n,r具有相同色多项式的图的必要条件.利用这些性质,得到了图Km,n,n(where 1≤m≤n)的色等价类.特别地,本文也证明了Km,n,n(2≤m≤n)能够由它们的色多项式唯一确定.