Many cliques with few edges and bounded maximum degree

DOI10.1016/J.JCTB.2021.05.005zbMath1472.05037arXiv2003.07943OpenAlexW3093801104MaRDI QIDQ1984508

Debsoumya Chakraborti, Da Qi Chen

Publication date: 16 September 2021

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

Abstract: Generalized Tur'an problems have been a central topic of study in extremal combinatorics throughout the last few decades. One such problem, maximizing the number of cliques of a fixed order in a graph with fixed number of vertices and bounded maximum degree, was recently completely resolved by Chase. Kirsch and Radcliffe raised a natural variant of this problem where the number of edges is fixed instead of the number of vertices. In this paper, we determine the maximum number of cliques of a fixed order in a graph with fixed number of edges and bounded maximum degree, resolving a conjecture by Kirsch and Radcliffe. We also give a complete characterization of the extremal graphs.

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

zbMATH Keywords

extremal graph theorycolexicographic graphsgeneralized Turán problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Vertex degrees (05C07)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Independent sets in graphs with given minimum degree
• Two problems on independent sets in graphs
• Face vectors of flag complexes
• The maximum number of q-cliques in a graph with no p-clique
• Many cliques with few edges
• Many triangles with few edges
• The maximum number of complete subgraphs in a graph with given maximum degree
• A generalization of a theorem of Turán
• The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree
• A New Method for Enumerating Independent Sets of a Fixed Size in General Graphs
• Shadows of colored complexes.
• The maximum number of triangles in a graph of given maximum degree
• Maximizing the Number of Independent Sets of a Fixed Size
• On Independent Sets in Graphs with Given Minimum Degree
• The History of Degenerate (Bipartite) Extremal Graph Problems
• Counting Independent Sets of a Fixed Size in Graphs with a Given Minimum Degree

Related Items (5)

Regular Turán numbers and some Gan–Loh–Sudakov‐type problems ⋮ Many Cliques in Bounded-Degree Hypergraphs ⋮ A spectral extremal problem on non-bipartite triangle-free graphs ⋮ Exact results on generalized Erdős-Gallai problems ⋮ A localized approach to generalized Turán problems

This page was built for publication: Many cliques with few edges and bounded maximum degree