Counting cliques in 1-planar graphs

DOI10.1016/j.ejc.2022.103654zbMath1505.05070arXiv2109.02906OpenAlexW3198906807MaRDI QIDQ2111191

J. Pascal Gollin, Xin Zhang, Kevin Hendrey, Abhishek Methuku, Casey Tompkins

Publication date: 28 December 2022

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

extremal graphsmaximum number of cliques of any fixed sizemaximum total number of cliques

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75)

Related Items (1)

On the edge-connectivity and restricted edge-connectivity of optimal 1-planar graphs

Uses Software

• plantri

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cliques in graphs excluding a complete graph minor
• Extremal problems for independent set enumeration
• On the maximum number of cliques in a graph embedded in a surface
• Rank-width and tree-width of \(H\)-minor-free graphs
• On the maximum number of five-cycles in a triangle-free graph
• Pentagons vs. triangles
• On the maximum number of cliques in a graph
• Bemerkungen zu einem Sechsfarbenproblem von G. Ringel
• Characterizing and recognizing 4-map graphs
• On the number of pentagons in triangle-free graphs
• Ein Sechsfarbenproblem auf der Kugel
• On the number of cliques in graphs with a forbidden minor
• An annotated bibliography on 1-planarity
• Algorithms for graphs embeddable with few crossings per edge
• Minimal non-1-planar graphs
• Proper minor-closed families are small
• Über eine Eigenschaft der ebenen Komplexe
• An Entropy Approach to the Hard-Core Model on Bipartite Graphs
• The Maximum Number of Triangles in C_2k+1-Free Graphs
• (1,λ)-EMBEDDED GRAPHS AND THE ACYCLIC EDGE CHOOSABILITY
• Re-embeddings of Maximum 1-Planar Graphs
• Über 1-optimale Graphen
• Number of Cliques in Graphs with a Forbidden Subdivision
• The Number of Independent Sets in a Regular Graph
• Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
• Arboricity and Subgraph Listing Algorithms
• Zur Struktur 1‐planarer Graphen
• Efficient Planarity Testing
• On the number of cycles of lengthk in a maximal planar graph
• Improvements on the density of maximal 1‐planar graphs
• Beyond Planar Graphs
• On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion
• Many \(T\) copies in \(H\)-free graphs
• Book embeddings of nonplanar graphs with small faces in few pages

This page was built for publication: Counting cliques in 1-planar graphs