禁用构型下边染色完全图的正常圈研究

作     者：刘甜 

作者单位：郑州大学 

学位级别：硕士

导师姓名：原晋江;黄飞

授予年度：2021年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：边染色完全图 单色三角形 单色P4 正常染色圈 退化集 

摘      要：给定一个边染色图Gc,它的一个子图被称为正常染色的,如果该子图的任意两条相邻的边都具有不同的颜色.Gc的一个子图被称为单色的,如果该子图所有的边都具有相同的颜色.Gc的最小色度,记作δc(Gc),定义为最大的非负整数δ使得Gc的每个顶点所关联的边上至少出现δ种不同的颜色.一个长度为3的圈被称为是一个三角形.Lo(2013)证明了:如果δc(Gc)≥ 2,那么Gc含有一条长度至少为2δc(Gc)的正常染色路或一个长度至少为δc(Gc)+1的正常染色圈.本学位论文在Lo(2013)的工作的基础上,对边染色完全图Knc的正常染色圈进行了研究.针对单色三角形或单色P4作为Knc的禁用构型的两种情形,我们分别得到下述结果:(1)设l1和l2分别是图Knc中的最短正常染色圈和最长正常染色圈的长度.如果Knc不含单色三角形,那么对于任一满足l1≤l≤l2的整数l,Knc包含一个长度为l的正常染色圈.此外,如果δc(Knc)=k≥2,那么l1≤4且l2≥ min{2k-1,n}.(2)如果Knc不含单色P4且δc(Knc)≥ 3,那么当n=4时,Knc是正常顶点泛圈的;当n≥5,对于任一满足4 ≤l ≤ n—1的整数l,Knc中每一顶点都包含在一个长度为l的正常染色圈中;否则存在V(Knc)的一个真子集作为Knc的退化集.