He, Zhen and Frankl, Péter and Győri, Ervin and Lv, Zequn and Salia, Nika and Tompkins, Casey and Varga, Kitti Katalin and Zhu, Xiutao (2024) Extremal Results for Graphs Avoiding a Rainbow Subgraph. ELECTRONIC JOURNAL OF COMBINATORICS, 31 (1). ISSN 1097-1440
|
Text
11676-PDFfile-48089-1-10-20240116.pdf Download (269kB) | Preview |
Abstract
We say that k graphs G1, G2, …, Gk on a common vertex set of size n contain a rainbow copy of a graph H if their union contains a copy of H with each edge belonging to a distinct Gi. We provide a counterexample to a conjecture of Frankl on the maximum product of the sizes of the edge sets of three graphs avoiding a rainbow triangle. We propose an alternative conjecture, which we prove under the additional assumption that the union of the three graphs is complete. Furthermore, we determine the maximum product of the sizes of the edge sets of three graphs or four graphs avoiding a rainbow path of length three. © The authors.
| Item Type: | Article |
|---|---|
| Additional Information: | School of Mathematics and Statistics, Beijing Jiaotong University, China Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Hungary Department of Mathematical Sciences, Tsinghua University, China King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Hungary ELKH-ELTE Egerváry Research Group, Hungary School of mathematics, Nanjing University of Aeronautics and Astronautics, China Export Date: 9 February 2024 Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFI, K135800 Funding details: National Research, Development and Innovation Office, K126853, K132696, SNN-135643 Funding text 1: We would like to thank the referees for their detailed remarks, which greatly improved the presentation of the paper. The research of Frankl, Gyo˝ri and Salia was partially supported by the National Research, Development and Innovation Office NKFIH, grants K132696, SNN-135643 and K126853. The research of Tompkins was supported by NKFIH grant K135800. |
| Uncontrolled Keywords: | Mathematics, Applied; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 05 Apr 2024 11:09 |
| Last Modified: | 05 Apr 2024 11:09 |
| URI: | https://real.mtak.hu/id/eprint/191864 |
Actions (login required)
 |
Edit Item |
