Pith. sign in

Extremal problems for a matching and any other graph

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
abstract

For a family of graphs $\F$, a graph is called $\F$-free if it does not contain any member of $\F$ as a subgraph. The generalized Tur\'an number $\ex(n,K_r,\F)$ is the maximum number of $K_r$ in an $n$-vertex $\F$-free graph and $\ex(n,K_2,\F)=\ex(n,\F)$, i.e., the classical Tur\'an number. Let $M_{s+1}$ be a matching on $s+1$ edges and $F$ be any graph. In this paper, we determine $\ex(n,K_r, \{M_{s+1},F\})$ apart from a constant additive term and also give a condition when the error constant term can be determined. In particular, we give the exact value of $\ex(n,\{M_{s+1},F\})$ for $F$ being any non-bipartite graph or some bipartite graphs. Furthermore, we determine $\ex(n,K_r,\{M_{s+1},F\})$ when $F$ is color critical with $\chi(F)\ge \max\{r+1,4\}$. These extend the results in [2,11,18].

fields

math.CO 1

years

2024 1

verdicts

CONDITIONAL 1

representative citing papers

Tur\'an numbers of cycles plus a general graph

math.CO · 2024-11-26 · conditional · novelty 6.0

The Turan number ex(n,{C>=k,F}) is determined up to an additive constant for every 2-connected F with p(F) at least floor((k-1)/2)+1; the even-k formula is n times the larger of (k-2)/2 and ex(k-1,F)/(k-2), plus O_k(1).

citing papers explorer

Showing 1 of 1 citing paper.

  • Tur\'an numbers of cycles plus a general graph math.CO · 2024-11-26 · conditional · none · ref 19 · internal anchor

    The Turan number ex(n,{C>=k,F}) is determined up to an additive constant for every 2-connected F with p(F) at least floor((k-1)/2)+1; the even-k formula is n times the larger of (k-2)/2 and ex(k-1,F)/(k-2), plus O_k(1).