论文部分内容阅读
本文涉及的图均为有限，非空，无向，简单图。本文主要研究了以下两方面的问题： 1．树的均匀着色。 2．完全Υ-部图的均匀着色。 称图G（V，E）是可均匀κ-着色的，如果可以用κ种颜色给G的顶点着色，使得相邻的顶点不同色且各色类的基数至多差1。称G可均匀κ-着色的最小整数κ为C的均匀色数，记为χe（G）。W.Meyer[2]在1973年提出了这个概念并提出了一个猜想：若G是连通图但不是完全图和齐圈，则χe（G）≤Δ（G），其中Δ（G）表示图C的最大度。Meyer的猜想对一些特殊图被证明是正确的，如二部图[6]，完全Υ-部图[13]，线图[13]，外平面图[8]，最大度不小于13的平面图[9]，最大度不小于顶点数一半或最大度不大于3的图[4]。关于图的均匀着色，B.Bollobás和R.K.Guy[5]证明了如果n≥3Δ-8或n=3Δ-10，则顶点数为n的树可均匀3-着色；A.Kostochka[26]证明了最大度不大于Δ的外平面图可均匀κ-着色，如果κ≥Δ／2+1；Sriram V.Pemmaraju[27]证明了n个顶点的外平面图可均匀6-着色，如果它的最大度不大于n／6。B.L.Chen和K.W.Lih[7]给出了不能均匀2-着色的树可均匀κ-着色的充要条件。由该条件的启发，我们得到了树可均匀κ-着色的其他条件。 定理1．设T是最大度为Δ的n个顶点的树，则T可均匀κ-着色的充要条件是存在一个点v，d（v）=Δ，使得α（T-N（v））≥|n／κ|-1。 定理2．设T=T（X，Y）是树且|X|=n≥m=|Y|。如果κ≥[n／（m+1）]，则T可均匀κ-着色，其中κ≥3。 定理3．如果T是最大度为Δ的树，则对任一顶点v，d（v）=Δ，T-v可均匀3-着色。 称树T是毛虫树，如果删去T的悬挂点及其关联的边后是路。该路称为毛虫树的脊线，记为Pm=v1v2…vm。设d（vi）=di，i=1，2，…，m，记毛虫树为T（山，己2，…，dm），记，=艺峨，b’一又d、云是奇数乞是偶数定理4.毛虫树可均匀2-当。是奇数时，O三。‘一乙着色的充要条件是当。是偶数时，{。’一乙’{三1;<2. 定理5.设到d‘，dZ，…，d司是最大度为△的二个顶点的毛虫树，则对凡全3，T可均匀k一着色，如果△三了nax{rZn/3几一b+l，fZ二/3{一二+2，f（。+10）/3{}除了当二=3△一9时△<。i可乙十5，。+4}，其中乙=m、吐乙‘一仁二/2」十1，。‘-「二/2{十1}. 设A二{a，，助，…，a二}是一个实数集‘称数对帆，aj)为A的序对，如果a;，a，:生且a*>a;.如果a:是奇数a，是偶数，称（a*，a，）是A的奇偶序对.称两个序对（a*，aj）和（as，at）是完全不同的，如果a*>a;>a，>at.o（A）表示A中完全不同的奇偶序对的最大数目.设凡二:，:2…阮是T的脊线.令={乞:。，任V（凡）且d（:*）全3}U{二}，称I是T的尸3一集 定理6.设T是最大度为△的。个顶点的毛虫树，则对于凡全3，T可均匀k一着色的充要条件是存在T的一个顶点、，d（:）=△，使得二一trz/到七「（二l十l）/2{十「（二2十l）/2)十O（11）+O（几）十△，其中T一N回是两个子毛虫树，即脊线为氏1二:，:2…阮t的T!和脊线为Prn。二试悦…嘛2的几，I、和12分别为Tl和几的p3一集. 二分树或者是空的（没有顶点），或者是有一个称为根的点和两个可能是空的子树，称为左子树和右子树.根点到叶子点的最长路的长度定义为二分树的深度.如果二分树的叶子点都在第。层或第m一1层，且第。层的叶子点都在左侧，则称为完全二分树.如果二分树的叶子点都在第。层且每个点都恰好有零个或两个孩子，则称为满二分树. 定理7.对于k全3，二分树可均匀k一着色. 定理8.深度为，几的完全二分树可均匀2一着色的充要条件是当7。是奇数时，2了n一’三。‘。‘三2“‘一‘+2:当二是偶数时，2‘不‘一’一2三‘乙7。三2爪一‘;其中。:，。为第了。层的顶点数. 推论9.深度为21。的满二分树可均匀2一着色的充要条件是。二、.设T是直径为4的树，则删去悬挂点及其关联的边后为一个星.记vo为T的中心，，Dl，刃2际为:。的邻点.设d（:*）=试，乞二为到:。;:1，:2，…，vrn)或到二;dl，dZ，…，d司. 定理10.设T=州二;dl，dZ，…，嘛)是直径为4的树1，2，…， 贝」T二，这样的树表示可均匀2一着色的充要条件是0三Zm-艺界T（:。、d:三2.定理11.设T=勺。;勺一，衫2，…:耐是直径为4的树，东着色的充要条件是存在T的一个顶点、，，以:。）二△ 则对于k全3，T可均匀使得“一L“/k;全{△，△十…姚…，如果否则，Ut=UO，其中谈={‘认:‘l（::）表示七2，，少:并:，亡，1三i三，r，}令域劝T中悬挂点的数目，创。)表示与顶点刀相邻的悬挂点的数叮（T）=。:，、{叮（。）:d（:）==△（T）}、定理12.设T=到X，均是直径为4的树，如果11xJ一y」卜1，则 一、，尸I币厂（T）{+1瓜川一饥叫3，临画万雨汗乏序 关于毛虫树，给出了两种计算均匀色数的方法.关于树的均匀k一着色，丸七3，给出了一个算法，并证明了其正确性和时间界. 定理13.算法E丸C在o（k·}州2·…y{）时间内给出树T的均匀k一着色，其中k全3. 如果?