Search ResultsShowing 1-3 of 3
-
arXiv:2005.02907 (Published 2020-05-06)
Regular Turán numbers of complete bipartite graphs
Categories: math.COLet $\mathrm{rex}(n, F)$ denote the maximum number of edges in an $n$-vertex graph that is regular and does not contain $F$ as a subgraph. We give lower bounds on $\mathrm{rex}(n, F)$, that are best possible up to a constant factor, when $F$ is one of $C_4$, $K_{2,t}$, $K_{3,3}$ or $K_{s,t}$ when $t>s!$.
-
arXiv:1911.08452 (Published 2019-11-19)
Regular Turán numbers and some Gan-Loh-Sudakov-type problems
Motivated by a Gan-Loh-Sudakov-type problem, we introduce the regular Tur\'an numbers, a natural variation on the classical Tur\'an numbers for which the host graph is required to be regular. Among other results, we prove a striking supersaturation version of Mantel's theorem in the case of a regular host graph of odd order. We also characterise the graphs for which the regular Tur\'an numbers behave classically or otherwise.
-
arXiv:1911.00109 (Published 2019-10-31)
Regular Turán numbers
The regular Tur\'an number of a graph $F$, denoted by rex$(n,F)$, is the largest number of edges in a regular graph $G$ of order $n$ such that $G$ does not contain subgraphs isomorphic to $F$. Giving a partial answer to a recent problem raised by Gerbner et al. [arXiv:1909.04980] we prove that rex$(n,F)$ asymptotically equals the (classical) Tur\'an number whenever the chromatic number of $F$ is at least four; but it is substantially different for some 3-chromatic graphs $F$ if $n$ is odd.