Campus Units

Mathematics

Document Type

Article

Publication Version

Submitted Manuscript

Publication Date

9-2017

Journal or Book Title

Journal of Combinatorial Theory, Series B

Volume

126

First Page

83

Last Page

113

DOI

10.1016/j.jctb.2017.04.002

Abstract

Erdős and Sós proposed the problem of determining the maximum number F(n) of rainbow triangles in 3-edge-colored complete graphs on n vertices. They conjectured that F(n) = F(a) + F(b) + F(c) + F(d) + abc + abd + acd + bcd, where a+b+c+d = n and a, b, c, d are as equal as possible. We prove that the conjectured recurrence holds for sufficiently large n. We also prove the conjecture for n = 4k for all k ≥ 0.

Comments

This article is published as Balogh, József, Ping Hu, Bernard Lidický, Florian Pfender, Jan Volec, and Michael Young. "Rainbow triangles in three-colored graphs." Journal of Combinatorial Theory, Series B (2017). 10.1016/j.jctb.2017.04.002 Posted with permission.

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Copyright Owner

Elsevier Inc.

Language

en

File Format

application/pdf

Available for download on Saturday, September 01, 2018

Published Version

Share

COinS