On a colored Turan problem of Diwan and Mubayi

J 2022

On a colored Turan problem of Diwan and Mubayi

LAMAISON VIDARTE, Ander, Alp MUYESSER a Michael TAIT

Základní údaje

Originální název

On a colored Turan problem of Diwan and Mubayi

Autoři

LAMAISON VIDARTE, Ander (724 Španělsko, domácí), Alp MUYESSER a Michael TAIT

Vydání

Discrete Mathematics, Elsevier B. V. 2022, 0012-365X

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Nizozemské království

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 0.800

Kód RIV

RIV/00216224:14330/22:00128972

Organizační jednotka

Fakulta informatiky

DOI

http://dx.doi.org/10.1016/j.disc.2022.113003

UT WoS

000831721100007

Klíčová slova anglicky

Turán number; Erdős-Stone theorem; Regularity

Změněno: 6. 4. 2023 11:32, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

Suppose that R (red) and B (blue) are two graphs on the same vertex set of size n, and H is some graph with a red-blue coloring of its edges. How large can R and B be if R∪B does not contain a copy of H? Call the largest such integer mex(n,H). This problem was introduced by Diwan and Mubayi, who conjectured that (except for a few specific exceptions) when H is a complete graph on k+1 vertices with any coloring of its edges mex(n,H)=ex(n,Kk+1). This conjecture generalizes Turán's theorem. Diwan and Mubayi also asked for an analogue of Erdős-Stone-Simonovits theorem in this context. We prove the following upper bound on the extremal threshold in terms of the chromatic number χ(H) and the reduced maximum matching number M(H) of H. [Formula presented] M(H) is, among the set of proper χ(H)-colorings of H, the largest set of disjoint pairs of color classes where each pair is connected by edges of just a single color. The result is also proved for more than 2 colors and is tight up to the implied constant factor. We also study mex(n,H) when H is a cycle with a red-blue coloring of its edges, and we show that [Formula presented], which is tight.

Citovat

LAMAISON VIDARTE, Ander, Alp MUYESSER a Michael TAIT. On a colored Turan problem of Diwan and Mubayi. Discrete Mathematics. Elsevier B. V., 2022, roč. 345, č. 10, s. 1-8. ISSN 0012-365X. Dostupné z: https://dx.doi.org/10.1016/j.disc.2022.113003.

@article{2273618,
   author = {Lamaison Vidarte, Ander and Muyesser, Alp and Tait, Michael},
   article_number = {10},
   doi = {http://dx.doi.org/10.1016/j.disc.2022.113003},
   keywords = {Turán number; Erdős-Stone theorem; Regularity},
   language = {eng},
   issn = {0012-365X},
   journal = {Discrete Mathematics},
   title = {On a colored Turan problem of Diwan and Mubayi},
   url = {https://doi.org/10.1016/j.disc.2022.113003},
   volume = {345},
   year = {2022}
}

TY  - JOUR
ID  - 2273618
AU  - Lamaison Vidarte, Ander - Muyesser, Alp - Tait, Michael
PY  - 2022
TI  - On a colored Turan problem of Diwan and Mubayi
JF  - Discrete Mathematics
VL  - 345
IS  - 10
SP  - 1-8
EP  - 1-8
PB  - Elsevier B. V.
SN  - 0012365X
KW  - Turán number
KW  - Erdős-Stone theorem
KW  - Regularity
UR  - https://doi.org/10.1016/j.disc.2022.113003
N2  - Suppose that R (red) and B (blue) are two graphs on the same vertex set of size n, and H is some graph with a red-blue coloring of its edges. How large can R and B be if R∪B does not contain a copy of H? Call the largest such integer mex(n,H). This problem was introduced by Diwan and Mubayi, who conjectured that (except for a few specific exceptions) when H is a complete graph on k+1 vertices with any coloring of its edges mex(n,H)=ex(n,Kk+1). This conjecture generalizes Turán's theorem. Diwan and Mubayi also asked for an analogue of Erdős-Stone-Simonovits theorem in this context. We prove the following upper bound on the extremal threshold in terms of the chromatic number χ(H) and the reduced maximum matching number M(H) of H. [Formula presented] M(H) is, among the set of proper χ(H)-colorings of H, the largest set of disjoint pairs of color classes where each pair is connected by edges of just a single color. The result is also proved for more than 2 colors and is tight up to the implied constant factor. We also study mex(n,H) when H is a cycle with a red-blue coloring of its edges, and we show that [Formula presented], which is tight.
ER  -

LAMAISON VIDARTE, Ander, Alp MUYESSER a Michael TAIT. On a colored Turan problem of Diwan and Mubayi. \textit{Discrete Mathematics}. Elsevier B. V., 2022, roč.~345, č.~10, s.~1-8. ISSN~0012-365X. Dostupné z: https://dx.doi.org/10.1016/j.disc.2022.113003.

Podrobný výpis o publikaci