We study a restriction of the classical Erd\H{o}s--S\'os problem, the extremal number of trees, to the class of bipartite host graphs, both when only the order of the host is prescribed and when its two part-sizes are fixed. We give natural lower-bound constructions and formulate corresponding linear upper-bound conjectures. We apply a weighted variant of $k$-minimality to prove upper bounds for a broad family of trees including brooms, trees with part-sizes obeying certain inequalities, and all trees on at most seven vertices, resolving part of a problem of Caro, Patk\'os and Tuza up to additive constants. We also relate the fixed-part extremal number of a tree to the ordinary extremal number, and consider an oriented bipartite extremal function analogous to the Zarankiewicz function.
For every natural number $r\geq 2$, we construct $r^{th}$ powers of bipartite graphs whose chromatic number is quadratic in their clique number, showing that the straightforward quadratic upper bound is best possible. We thereby settle an open problem posed by Chakraborty, Chandran, Jacob and Pillai [J. Graph Theory 11...
We prove that Pyber's upper bound $2^{O(n\log(n))}$ for the number of minimally transitive subgroups of $S_n$ is best possible along the powers of every fixed prime, even when the groups are counted up to permutational isomorphism. As a byproduct, our construction shows that, along the powers of every fixed prime, the...
We introduce and study a finite simple graph of algebraic origin: the Vieta graph on the solution set over $\mathbb{F}_p$ to a symmetric, multivariate equation which is quadratic in each variable. This construction is a broad generalization of the Markoff graph over $\mathbb{F}_p$, extensively studied in the recent lit...
The chromatic threshold, originating in a question of Erd\H{o}s and Simonovits, asks when a linear minimum-degree condition forces bounded chromatic number in H-free graphs. Motivated by a question of Thomassen, the homomorphism threshold asks for the stronger conclusion that every such graph admits a homomorphism to a...
Xin-Qi Huang, Mingyuan Rong, C. Shangguan· 1 citation
In 1943, Hadwiger formulated his celebrated conjecture, connecting the chromatic number $\chi(G)$ of a finite, simple, undirected graph with the cardinality of the largest complete minor, $\eta(G)$. The disjoint union of all finite complete graphs shows that Hadwiger's conjecture fails for infinite, but a slightly weak...
For a graph and a graph family , let denote the maximum number of copies of in an ‐free ‐vertex graph. Let . Bai, Tompkins, and Well conjectured that is attained if and each block of the graph is a . In this paper, we determine the exact value of and the extremal graphs for all . The novelty of our proof is to give a...
Xiaojun Zhao, Yuejian Peng· Journal of Graph Theory· 2 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
