Extremal Results for Graphs Avoiding a Rainbow Subgraph

Zhen He; Peter Frankl; Ervin Győri; Zequn Lv; Nika Salia; Casey Tompkins; Kitti Varga; Xiutao Zhu

doi:10.37236/11676

Extremal Results for Graphs Avoiding a Rainbow Subgraph

Zhen He
, Peter Frankl
, Ervin Győri
, Zequn Lv
, Nika Salia
, Casey Tompkins
, Kitti Varga
, Xiutao Zhu

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

6 Scopus citations

Abstract

We say that k graphs G₁, G₂, …, G_k 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 G_i. 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.

Original language	English
Journal	Electronic Journal of Combinatorics
Volume	31
Issue number	1
DOIs	https://doi.org/10.37236/11676
State	Published - 2024

Bibliographical note

Publisher Copyright:
© The authors.

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.37236/11676

Cite this

@article{278853db889946299f0fa8d5a067dfbf,

title = "Extremal Results for Graphs Avoiding a Rainbow Subgraph",

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.",

author = "Zhen He and Peter Frankl and Ervin Gy{\H o}ri and Zequn Lv and Nika Salia and Casey Tompkins and Kitti Varga and Xiutao Zhu",

note = "Publisher Copyright: {\textcopyright} The authors.",

year = "2024",

doi = "10.37236/11676",

language = "English",

volume = "31",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Australian National University",

number = "1",

}

TY - JOUR

T1 - Extremal Results for Graphs Avoiding a Rainbow Subgraph

AU - He, Zhen

AU - Frankl, Peter

AU - Győri, Ervin

AU - Lv, Zequn

AU - Salia, Nika

AU - Tompkins, Casey

AU - Varga, Kitti

AU - Zhu, Xiutao

PY - 2024

Y1 - 2024

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/85183439968

U2 - 10.37236/11676

DO - 10.37236/11676

M3 - Article

AN - SCOPUS:85183439968

SN - 1077-8926

VL - 31

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 1

ER -

Extremal Results for Graphs Avoiding a Rainbow Subgraph

Abstract

Bibliographical note

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this