论文部分内容阅读
设G是简单图，用颜色1，2，3，…对G进行正常边着色.如果每一个顶点上表现的颜色都构成一个连续的整数集合，那么就称这个边着色是连续的.图G的亏度def(G)是粘在G上使结果图可连续边着色的悬挂边的最小数目.本文分为三章，主要研究了两类图的连续边着色. 第一章对本文所用的术语、记号作了介绍. 第二章第一节给出了连续边着色的几个一般结论.设G1，G2和S是图G的子图，且满足G=G1∪ G2和S=G1∩ G2，那么就称G为沿着S粘接G1和G2得到的图.特别地，若S=K1且V(S)={v}，则称图G是在一个顶点v上粘接G1和G2得到的，记作G=G1∨vG2.树圈图是每条边至多属于一个圈的连通图.特殊地，称由若干个圈在同一个顶点粘接得到的树圈图为花图.第二章第二节主要研究了树圈图的连续边着色，得到了以下结果: 定理2.2.7设G是一个花图，则def(G)={1,ε(G)为奇数;0,ε(G)为偶数. 定理2.2.9设G=G1∨wG2，其中G1，G2是花图，则def(G)={1,ε(G)为奇数;0,ε(G)为偶数. 定理2.2.10设G是由若干个圈粘接得到的树圈图.若ε(G)为奇数，则def(G)≥1. 定理2.2.11设G是由在一个奇圈的每个顶点上粘接一个奇圈得到的树圈图，则def(G)=1. 定理2.2.12设G是在一个奇圈除一个顶点外的每个顶点上粘接一个奇圈得到的树圈图，则def(G)=1. 设P1，P2，…，Pm是从上到下依次排列的m(m≥4)条长为n-1(n≥3）的路，第i条路上的顶点依次为vi1，vi2，…，vin（1≤i≤m），则称连结顶点vj与vi+1，j，vi+3,j+2(1≤j≤n)得到的图为m×n图（如图1）.第三章证明了方格图是可连续边着色的.