文档介绍：k色图的连通性()()JOURNALOFNORTHUNIVERSITYOFCHINANATURALSCIENCEEDITION()()文章编号:16732319320080220101204Ξ色图的连通性123徐述,欧阳剑新,石胜坤(,北京100072;,北京100016;),北京100871摘要:研究和讨论了图的顶点着色问题中色图的连通性,利用归纳与迭代的方法证明了对于任何色kkk(),使得对该着色类中任意顶点集所诱导出的的子,连通图,存在顶点的一个着色,,XkXiGGVGX1X2k(),:顶点着色;色图;连通性k中图分类号::OA-TheConnectivityofChromaticGraphs123,2,2XUShuOUYANGJianxinSHIShengkun(,,100072,;.,100016,;MicrolinkInternationalSoftwareCorpBeijingChina)3.,,100871,SchoolofMathematicalSciencesPekingUniversityBeijingChina2:.,AbstractTheconnectivityofkchromaticgraphswerediscussedByinductionanditerationitwas)(2,,,,XkofVprovedthatforanyconnectedkchromaticgraphGthereexistsakcoloringX1X2Gk().,.:;2;Keywordsvertexcoloringkchromaticgraphconnectivity1概述(),,2,,对于的顶点的一个分配;称着色GVEGkkkG是正常的,()个独立集的一个分类,,,.当有一个正常顶点着色时,()方便起见,把“正常顶点着色”,()关于图的顶点着色的更多内容可参见文献1,2.=,()()()记为一个图,,其满足,}?如GmGGmVG=VG,{uvEG,()))表示由顶点集合诱导出的((GX果,?.这里,表示和在图中的距离;XGdistuvmdistuvuvGmm();,k()中探索了使得如下条件成立的最小正整数:对给定的正整数,,和在文献4fkkChenSchelpShreveΞ收稿日期:2007211210()作者简介:徐述19622,男,研究员,.()中北大学学报自然科学版1022008年第2期()kf()每个色连通图,存在一个以,,,为着色类的着色,使得Xi是连通的对所有成kGX1X2XkkGi()()?-2条边组成的路径连接起来的两个阶完全图使得?,fkkkkfkk作了如下推测4推测1()记为一个阶色连通图,对于充分大的仅依赖于,存在的一个以,,,XkGnknkGX1X2k()()为着色类的着色,使得对所有的1??()()(()())文献4中给出了k的一个上界fk?12k-21,当IVGI?kk-2+.()()定理1对于任何色连通图,存在的着色,,,,使得对所有的1??有kGVGX1X2Xkiikk()()首先=1或2时,=3和?=3时的重新着色算法k设为一个3色连通图,,,