Note on edge-colored graphs and digraphs without properly colored cycles

Details Note on edge-colored graphs and digraphs without properly colored cycles Note on edge-colored graphs and digraphs without properly colored cycles

2007-07-31

arxiv.org/abs/0707.4580v1

Computer Science

Discrete Mathematics

Scientific paper

We study the following two functions: d(n,c) and $\vec{d}(n,c)$; d(n,c) ($\vec{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)\ge {1 \over c}(\log_cn -\log_c\log_cn)$ and, thus, the conjecture does not hold. In particular, this inequality significantly improves a lower bound on $\vec{d}(n,2)$ obtained by Gutin, Sudakov and Yeo in 1998.

Affiliated with

Also associated with

No associations

Rating

Note on edge-colored graphs and digraphs without properly colored cycles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Note on edge-colored graphs and digraphs without properly colored cycles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Note on edge-colored graphs and digraphs without properly colored cycles will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-222462