Abstract
For an edge-colored graph, its minimum color degree is the minimum number of distinct colors appearing on the edges incident with a vertex, and its maximum monochromatic degree is the maximum number of edges with the same color incident with a vertex. A cycle in an edge-colored graph is called properly colored if any two consecutive edges of the cycle have distinct colors. We investigate sufficient conditions in terms of the minimum color degree and maximum monochromatic degree for the existence of short properly colored cycles in edge-colored complete graphs. In particular, we obtain sharp results for the existence of properly colored C4’s, and we characterize the extremal graphs for several known results on the existence of properly colored triangles. Moreover, we obtain sharp sufficient conditions guaranteeing that every vertex is contained in a properly colored triangle or C4, respectively.
| Original language | English |
|---|---|
| Pages (from-to) | 101-109 |
| Number of pages | 9 |
| Journal | Discrete Applied Mathematics |
| Volume | 327 |
| DOIs | |
| State | Published - 15 Mar 2023 |
Keywords
- (Total) color degree
- (Total) monochromatic degree
- Edge-colored complete graph
- Properly colored triangle and C
Fingerprint
Dive into the research topics of 'Sufficient conditions for properly colored C3’s and C4’s in edge-colored complete graphs'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver