Sufficient conditions for properly colored C3’s and C4’s in edge-colored complete graphs

Tingting Han, Hajo Broersma, Yandong Bai, Shenggui Zhang

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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 languageEnglish
Pages (from-to)101-109
Number of pages9
JournalDiscrete Applied Mathematics
Volume327
DOIs
StatePublished - 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