How to find all extremal graphs using symmetric subgraphs

Abstract

Let $\mathcal{F}$ be a finite family of graphs with ${\min }_{F\in \mathcal{F}}\chi (F)=r+1\ge 3$, where $\chi (F)$ is the chromatic number of $F$. Set $t={\max }_{F\in \mathcal{F}}|F|$. Let $\mathrm{EX}(n,\mathcal{F})$ be the set of graphs with maximum edges among all the graphs of order $n$ without any $F\in \mathcal{F}$ as a subgraph. Let $T(n,r)$ be the Turán graph of order $n$ with $r$ parts. Assume that some $F_0\subseteq \mathcal{F}$ is a subgraph of the graph obtained from $T(rt,r)$ by embedding a path in its one part. Simonovits \cite{S1} introduced the concept of symmetric subgraphs, and proved that there exist graphs in $\mathrm{EX}(n,\mathcal{F})$ which have symmetrical property. In this paper, we aim to find a way to characterize all the extremal graphs for such $\mathcal{F}$ using symmetric subgraphs. Some new extremal results are obtained.