2007/07/31 by Gregory Gutin, Gutin, Gregory
Computer Science · Mathematics · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.2 #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #cs.DM
paper · pdf · doi:10.48550/arxiv.0707.4580
arxiv created 2007/07/31 · openalex publication_date 2007/07/31 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the following two functions: d(n,c) and d(n,c); 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 \over c(logcn -logclogcn) 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.