不含三角形图的正常染色路和正常染色圈

摘要

图G为边染色图,对G中的任一顶点v,定义v的色度dc(v):G中与顶点v相关联的边中不同染色的数目.用δc(G)表示图G的最小色度,即δc(G)=min{dc(v):v∈G｝.若图G为不含三角形的边染色图,且δc(G)≥2,则G含长为4d-2的正常染色路或长至少为2d-2的正常染色圈.