摘要: 图G为边染色图, 对G中的任一顶点v, 定义v的色度d^c(v): $G$中与顶点$v$相关联的边中不同染色的数目. 用$\delta^c(G)$\,表示图$G$的最小色度, 即$\delta^c(G)={\rm min}\{d^c(v):v\in G\}$. 若图$G$为不含三角形的边染色图, 且$\delta^c(G)\geq 2$, 则$G$含长为$4d 2$的正常染色路或长至少为$2d-2$的正常染色圈.
中图分类号:
丁录顺, 王光辉, 颜谨. 不含三角形图的正常染色路和正常染色圈[J]. 运筹学学报, 2014, 18(3): 116-120.
DING Lushun, WANG Guanghui, YAN Jin. The properly colored paths and cycles for the triangle-free graphs[J]. Operations Research Transactions, 2014, 18(3): 116-120.