Properly colored and rainbow C4' S in edge-colored graphs

Fangfang Wu, Hajo Broersma*, Shenggui Zhang, Binlong Li

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
38 Downloads (Pure)

Abstract

We present new sharp sufficient conditions for the existence of properly colored and rainbow (Formula presented.) 's in edge-colored graphs. Our first results deal with sharp color neighborhood conditions for the existence of properly colored (Formula presented.) 's in edge-colored complete graphs and complete bipartite graphs, respectively. Next, we characterize the extremal graphs for an anti-Ramsey number result due to Alon on the existence of rainbow (Formula presented.) 's in edge-colored complete graphs. We also generalize Alon's result from complete to general edge-colored graphs. Finally, we derive a structural property regarding the extremal graphs for a bipartite counterpart of Alon's result due to Axenovich, Jiang, and Kündgen on the existence of rainbow (Formula presented.) 's in edge-colored complete bipartite graphs. We also generalize their result from complete to general bipartite edge-colored graphs.

Original languageEnglish
Pages (from-to)110-135
Number of pages26
JournalJournal of graph theory
Volume105
Issue number1
Early online date9 Aug 2023
DOIs
Publication statusPublished - Jan 2024

Keywords

  • UT-Hybrid-D
  • extremal graph
  • properly colored C
  • rainbow C
  • the sum of edge number and color number
  • color neighborhood

Fingerprint

Dive into the research topics of 'Properly colored and rainbow C4' S in edge-colored graphs'. Together they form a unique fingerprint.

Cite this