d-退化图松弛均匀着色的一个注记(英文)

松弛均匀着色是松弛着色的一类特殊情况,它要求任意两个色类的顶点数之差至多为1.d-退化图是指每个导出子图都存在度至多为d的顶点的图.证明了若顶点数位n的d-退化图G的最大度至多为△,且K≥18d,n≥17△.则G存在均匀(k-1,1)着色.

反d-退化图中的点不交3-圈

如果图G的补图G是d-退化图,则称图G是反d-退化图。证明了当|G|=3k且δ(G)≥k≥26d时,反d-退化图G包含k个点不交的3-圈,其中d≥2。