Turán graphs with bounded matching number

DOI10.1016/J.JCTB.2023.12.002MaRDI QIDQ6187350zbMATH OpenFDO

Authors Noga Alon, Peter Frankl

Publication date 15 January 2024

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2210.15076

zbMATH Keywords

clique numbermatching numberTuran graphs

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We determine the maximum possible number of edges of a graph with $n$ vertices, matching number at most $s$ and clique number at most $k$ for all admissible values of the parameters.

Recommendations

• On Turán problems with bounded matching number
• On the maximum number of edges in hypergraphs with fixed matching and clique number
• Maximizing the number of cliques in graphs with given matching number
• On the maximum number of edges in a hypergraph with given matching number
• Graphs with restricted valency and matching number

Cites work

• scientific article; zbMATH DE number 3262986 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• scientific article; zbMATH DE number 3050594 (Why is no real title available?)
• Intersection theorems for systems of sets
• Matching theory
• On maximal paths and circuits of graphs

Cited in

(29)

• On the maximum number of edges in chordal graphs of bounded degree and matching number
• On Turán problems with bounded matching number
• A note on the stability results of the number of cliques in graphs with given matching number
• Generalized Turán problem with bounded matching number
• Extremal graphs with bounded matching number: a short proof of the Alon-Frankl theorem
• Spectral extrema of graphs: forbidden linear forests and non-bipartite graphs
• Spectral extrema of graphs: forbidden cliques and star forests
• On the matching problem in random hypergraphs
• A spectral generalized Alon-Frankl theorem
• Linear Turán problems with bounded matching number in hypergraphs
• The maximum number of cliques in graphs with given fractional matching number and minimum degree
• On generalized Turán number of graphs with bounded matching number
• The number of edges in graphs with bounded clique number and circumference
• Extremal graphs for star forests with bounded clique number
• Turán number of complete bipartite graphs with bounded matching number
• On hypergraph Turán problems with bounded matching number
• The maximum number of edges in a \(\{K_{r+1},M_{k+1}\}\)-free graph
• Extremal problems for a matching and any other graph
• Spectral extremal problems for graphs with bounded clique number
• Maximum size of a graph with given matching number and covering number
• Turán numbers of cycles plus a general graph
• The number of stars in a graph that forbids a matching and any graph
• Many cliques in graphs with bounded matching number and circumference
• Eigenvalues and factors: a survey
• Stable structure and extremal eigenvalues of degenerate Turán problems
• Exact results for generalized Turán number of a linear forest and a clique
• Turán number with bounded matching in \(K_{2,t}\)-free graph
• Generalized Turán problems for a matching and long cycles
• The exact Turán number of \(K_4^{3 -}\) with small bounded matching number

This page was built for publication: Turán graphs with bounded matching number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6187350)