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 language | English |
---|---|
Pages (from-to) | 110-135 |
Number of pages | 26 |
Journal | Journal of graph theory |
Volume | 105 |
Issue number | 1 |
Early online date | 9 Aug 2023 |
DOIs | |
Publication status | Published - Jan 2024 |
Keywords
- UT-Hybrid-D
- extremal graph
- properly colored C
- rainbow C
- the sum of edge number and color number
- color neighborhood