几类笛卡尔积图的关联色数研究.pdfVIP

第 25卷 第 6期 山东 建 筑 大 学 学 报 Vo1．25 No．6 2010征 12月 JOURNAL OF SHANDONG JIANZHU UNIVERSITY Dec． 2010 文章编号：1673—7644(2010)06—0572—04 几类笛卡尔积 图的关联色数研究 董桂香 ，尤海燕 ，许广镇 (1．山东建筑大学 理学院，山东 济南250101；2．济南市党家中学 教学组，山东 济南 250116) 摘要：图的关联着色问题是图着色理论的重要组成部分之一，确定图的关联色数是一个具有重要的实际价值和 理论意义的课题，关于图的关联着色还没有十分深刻的结果，研究 了路与完全二部图的笛卡尔积图的关联着 色、圈与完全二部图的笛卡尔积图的关联着色、完全图与完全二部图的笛卡尔积图的关联着色，根据笛卡尔积 网的特点，采用穷染的方法确定了其中部分图类的关联色数 ，从而验证了关联着色猜想在这些笛卡尔积图类中 是正确的。 关键词：笛卡尔积；关联着色；关联色数 中图分类号：0157．5 文献标识码 ：A Researchontheincidencechromaticnumbersofsome classesofCartesianproductgraphs DONG Gui—xiang ，YOU Hai—yan ，XU Guang．zhen (1．SchoolofScience，ShandongJianzhuUniversity，Jinan250101，China；2．ScienceOffice，DangfiaMiddleSchoolof JinanCity，Jinan250116，China) Abstract：Theincidencecoloringofgraphisan importantpartofthegraph coloringtheoryand the topicfordeterminingtheincidencechromaticnumberofgraphsisofgreatpracticalandtheoreticalsig— nificance．However，thereisnoveryprofoundresultabouttheincidencecoloringofgraph．Inthispa— per，theincidencecoloringofCartesian productofpath and completebipartitergaph，ofCartesian productofcycleandcompletebipartitegraph，ofCartesian productofcompletegraphand complete bipartitergapharestudied．BythepropertiesoftheseCartesianproductgraphs，theincidencechro— maticnumbersofsomeoftheseCartesianproductsareobtained．Theseresultsverifiedtheconjecture oftheincidencecoloringintheseCartesianproductgraphs． Keywords：Cartesianproduct；incidencecoloring；incidencechromaticnumber 0 引言 表示。凡文中未加说明的术语和记号可在文献[1] 中找到。 本文所研究的图都是有限、简单、无向图，设 G 设G=(V，E)是具有顶点集 和边集 E的一个 是一个图，其顶点集，边集