Color degree and monochromatic degree conditions for short properly colored cycles in edge-colored graphs

Shinya Fujita, Ruonan Li, Shenggui Zhang

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

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 languageEnglish
Pages (from-to)362-373
Number of pages12
JournalJournal of Graph Theory
Volume87
Issue number3
DOIs
StatePublished - Mar 2018

Keywords

  • 05C15
  • 05C38
  • complete (bipartite) graphs
  • edge-colored graphs
  • maximum monochromatic degree
  • minimum color degree
  • properly colored cycles

Fingerprint

Dive into the research topics of 'Color degree and monochromatic degree conditions for short properly colored cycles in edge-colored graphs'. Together they form a unique fingerprint.

Cite this