Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.07954 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911549320331264 |
|---|---|
| author | Zhang, Wenqian |
| author_facet | Zhang, Wenqian |
| contents | Let $\mathcal{F}$ be a finite family of graphs with $\min_{F\in \mathcal{F}}χ(F)=r+1\geq3$, where $χ(F)$ is the chromatic number of $F$. Set $t=\max_{F\in\mathcal{F}}|F|$. Let ${\rm 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 ${\rm 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_07954 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | How to find all extremal graphs using symmetric subgraphs Zhang, Wenqian Combinatorics Let $\mathcal{F}$ be a finite family of graphs with $\min_{F\in \mathcal{F}}χ(F)=r+1\geq3$, where $χ(F)$ is the chromatic number of $F$. Set $t=\max_{F\in\mathcal{F}}|F|$. Let ${\rm 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 ${\rm 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. |
| title | How to find all extremal graphs using symmetric subgraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2509.07954 |