Rainbow Turán numbers for paths of length four
Abstract
Given a set V of n vertices and an integer k≥1, our goal is to maximize the number of edges in graphs G1, G2, …, Gk, defined on V, under the constraint that the union of all graphs, thought of as a multi-graph, does not contain a rainbow copy of the path P5 on $5$ vertices, that is, a copy of P5 with each of its four edges belonging to a different Gi. We consider two versions of the problem, in which, respectively, ∑i e(Gi) and mini e(Gi) is maximized. In the former case, we determine the maximum precisely for all k≤ n−1 (and also for P4). In the latter, we obtain an asymptotic value for k∈{5,6,9} and formulate a very plausible conjecture for all other values of k. We also solve the problem for k=4, but under an additional assumption of completeness.
Related
BibTeX
@misc{antoniuk2026rainbow,
title = {{Rainbow Turán numbers for paths of length four}},
author = {Sylwia Antoniuk and Andrzej Grzesik and Magdalena Prorok and Andrzej Ruciński},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.25079},
eprint = {2608.25079},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.25079},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Rainbow Turán numbers for paths of length four
AU - Sylwia Antoniuk
AU - Andrzej Grzesik
AU - Magdalena Prorok
AU - Andrzej Ruciński
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2608.25079
UR - https://arxiv.org/abs/2608.25079
AB - Given a set V of n vertices and an integer k≥1, our goal is to maximize the number of edges in graphs G_1, G_2, …, G_k, defined on V, under the constraint that the union of all graphs, thought of as a multi-graph, does not contain a rainbow copy of the path P_5 on $5$ vertices, that is, a copy of P_5 with each of its four edges belonging to a different G_i. We consider two versions of the problem, in which, respectively, ∑_i e(G_i) and min_i e(G_i) is maximized. In the former case, we determine the maximum precisely for all k≤ n−1 (and also for P_4). In the latter, we obtain an asymptotic value for k∈{5,6,9} and formulate a very plausible conjecture for all other values of k. We also solve the problem for k=4, but under an additional assumption of completeness.
ER -