On a colored Turan problem of Diwan and Mubayi

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F22%3A00128972" target="_blank" >RIV/00216224:14330/22:00128972 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1016/j.disc.2022.113003" target="_blank" >https://doi.org/10.1016/j.disc.2022.113003</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.disc.2022.113003" target="_blank" >10.1016/j.disc.2022.113003</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On a colored Turan problem of Diwan and Mubayi

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

On a colored Turan problem of Diwan and Mubayi

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Discrete Mathematics

ISSN

0012-365X

e-ISSN

1872-681X

Svazek periodika

345

Číslo periodika v rámci svazku

10

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

8

Strana od-do

1-8

Kód UT WoS článku

000831721100007

EID výsledku v databázi Scopus

2-s2.0-85131551550