Operations Research Transactions ›› 2014, Vol. 18 ›› Issue (3): 116-120.

• Original Articles • Previous Articles    

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

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

CLC Number: