运筹学学报 ›› 2014, Vol. 18 ›› Issue (3): 116-120.

• 运筹学 • 上一篇    

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

丁录顺, 王光辉, 颜谨   

  1. 1. 山东大学数学学院, 济南 250100
  • 出版日期:2014-09-15 发布日期:2014-09-15
  • 通讯作者: 颜谨 E-mail:yanj@sdu.edu.cn
  • 基金资助:

    国家自然科学基金(No. 11271230), 山东省自然科学基金(No. ZR2012AM023)

The properly colored paths and cycles for the triangle-free graphs

DING Lushun1, WANG Guanghui1, YAN Jin1,*   

  1. 1. School of Mathematics, Shandong University, Jinan 250100, China
  • Online:2014-09-15 Published:2014-09-15

摘要: 图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$的正常染色圈.

关键词: 图, 正常染色路, 正常染色圈

Abstract: Let $G$ be an edge colored graph, $v$ be a vertex in $G$. $d^c(v)$ denotes the color degree of a vertex $v$, i.e. the number of edges with distinct colors incident to $v$. At the same time, $\delta^c(G)$ denotes the minimum color degree of $G$, i.e. $\delta^c(G)={\rm min}\{d^c(v):v\in G\}$. Let $G$ be an edge colored triangle-free graph  such that $\delta^c(G)\geq 2$. We prove that $G$ contains a properly colored path of length $4d-2$ or a properly colored cycle of length at least $2d-2$.

Key words: graph, properly colored path, properly colored cycle

中图分类号: