We study the following two functions: d(n, c )a nd� d(n, c); here d(n, c) ( � d(n, c)) is the minimum number k such that every c-edge-colored undirected (directed) graph of order n and minimum monochromatic degree (out-degree) at least k has a properly colored cycle. Abouelaoualim et al. (2007) stated a conjecture which implies that d(n, c )=1 . Using a recursive construction of c-edge-colored graphs with minimum monochromatic degree p and without properly colored cycles, we show that d(n, c) ≥ 1 c (logc n − logc logc n) and, thus, the conjecture does not hold. In particular, this inequality significantly improves a lower bound on � d(n, 2) obtained by Gutin, Sudakov and Yeo in 1998.
['Gregory Gutin']
Note on edge-colored graphs and digraphs without properly colored cycles