Extremal Problems for a Matching and Any Other Graph

Abstract

ABSTRACT For a family of graphs , a graph is called ‐free if it does not contain any member of as a subgraph. The generalized Turán number is the maximum number of in an ‐vertex ‐free graph and , that is, the classical Turán number. Let be a matching on edges and be any graph. In this paper, we determine 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 for being any non‐bipartite graph or some bipartite graphs. Furthermore, we determine when is color critical with .

Locations

• Journal of Graph Theory - View
• arXiv (Cornell University) - View - PDF