356. Extremal graphs for star forests with bounded clique number
Invited abstract in session MC-4: Data science meets strongly NP-Hard CO, stream Data Science meets Optimization.
Monday, 12:30-14:00Room: Rupert Beckett LT
Authors (first author is the speaker)
| 1. | Liying Kang
|
| Department of Mathematics, Shanghai University |
Abstract
Let $\mathcal{F}$ be a family of graphs. The Tur\'{a}n number ex$(n, \mathcal{F})$ of $\mathcal{F}$ is the maximum possible number of edges in an $n$-vertex graph that contains no member of $\mathcal{F}$ as a
subgraph. The study of Tur\'{a}n number of graphs is a central
topic in extremal graph theory.
Recently, Alon and Frankl determined the exact value of ex$(n, \mathcal{F})$ when $\mathcal{F}=\{K_{k+1},M_{s+1}\}$, where $K_{k+1}$ is the $(k+1)$-clique and $M_{s+1}$ is the $(s+1)$-matching.
Let $tS_l$ be the disjoint union of $t$ copies of the star $S_l$.
In this talk we determine the exact value of ex$(n, \mathcal{F})$ when $\mathcal{F}=\{K_{k+1},(s+1)S_l\}$ and all the extremal graphs for sufficiently large $n$.
Keywords
- Graphs and Networks
- Combinatorial Optimization
Status: accepted
Back to the list of papers