Abstract
For an edge-colored graph, its minimum color degree is defined as the minimum number of colors appearing on the edges incident to a vertex and its maximum monochromatic degree is defined as the maximum number of edges incident to a vertex with a same color. A cycle is called properly colored if every two of its adjacent edges have distinct colors. In this article, we first give a minimum color degree condition for the existence of properly colored cycles, then obtain the minimum color degree condition for an edge-colored complete graph to contain properly colored triangles. Afterwards, we characterize the structure of an edge-colored complete bipartite graph without containing properly colored cycles of length 4 and give the minimum color degree and maximum monochromatic degree conditions for an edge-colored complete bipartite graph to contain properly colored cycles of length 4, and those passing through a given vertex or edge, respectively.
Original language | English |
---|---|
Pages (from-to) | 362-373 |
Number of pages | 12 |
Journal | Journal of graph theory |
Volume | 87 |
Issue number | 3 |
DOIs | |
Publication status | Published - 1 Mar 2018 |
Keywords
- UT-Hybrid-D
- 05C38
- complete (bipartite) graphs
- edge-colored graphs
- maximum monochromatic degree
- minimum color degree
- properly colored cycles
- 05C15
- n/a OA procedure