Extremal H-free planar graphs

MaRDI QIDQ2415071zbMATH OpenFDO

Authors Yongxin Lan, Yongtang Shi, Z. X. Song

Publication date 20 May 2019

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.01487, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i2p11

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35)

Abstract: Given a graph $H$, a graph is $H$-free if it does not contain $H$ as a subgraph. We continue to study the topic of "extremal" planar graphs, that is, how many edges can an $H$-free planar graph on $n$ vertices have? We define $e{x}_{{}_{m}athcalP}(n,H)$ to be the maximum number of edges in an $H$-free planar graph on $n$ vertices. We first obtain several sufficient conditions on $H$ which yield $e{x}_{{}_{m}athcalP}(n,H)=3n-6$ for all $nge|V(H)|$. We discover that the chromatic number of $H$ does not play a role, as in the celebrated ErdH{o}s-Stone Theorem. We then completely determine $e{x}_{{}_{m}athcalP}(n,H)$ when $H$ is a wheel or a star. Finally, we examine the case when $H$ is a $(t,r)$-fan, that is, $H$ is isomorphic to $K_1+t{K}_{r-1}$, where $tge2$ and $rge3$ are integers. However, determining $e{x}_{{}_{m}athcalP}(n,H)$, when $H$ is a planar subcubic graph, remains wide open.

Review text

Summary: Given a graph \(H\), a graph is \(H\)-\textit{free} if it does not contain \(H\) as a subgraph. We continue to study the topic of ``extremal planar graphs initiated by \textit{C. Dowden} [J. Graph Theory 83, No. 3, 213--230 (2016; Zbl 1401.05079)], that is, how many edges can an \(H\)-free planar graph on $n$ vertices have? We define \(\mathrm{ex}_{\mathcal{P}}(n,H)\) to be the maximum number of edges in an \(H\)-free planar graph on \(n\) vertices. We first obtain several sufficient conditions on \(H\) which yield \(\mathrm{ex}_{\mathcal{P}}(n,H)=3n-6\) for all \(n\ge |V(H)|\). We discover that the chromatic number of \(H\) does not play a role, as in the celebrated Erdős-Stone Theorem. We then completely determine \(\mathrm{ex}_{\mathcal{P}}(n,H)\) when \(H\) is a wheel or a star. Finally, we examine the case when \(H\) is a \((t, r)\)-fan, that is, \(H\) is isomorphic to \(K_1+tK_{r-1}\), where \(t\ge 2\) and \(r\ge 3\) are integers. However, determining \(\mathrm{ex}_{\mathcal{P}}(n,H)\), when \(H\) is a planar subcubic graph, remains wide open.

Recommendations

• Extremal \(C_{4}\)-free/\(C_{5}\)-free planar graphs
• Extremal Theta-free planar graphs
• Planar Turán numbers of short paths
• Planar Turán number of the 6-cycle
• Planar Turán numbers on short cycles of consecutive lengths

Cites work

• A note on Turán numbers for even wheels
• Exact solution of the hypergraph Turán problem for k-uniform linear paths
• Extremal \(C_{4}\)-free/\(C_{5}\)-free planar graphs
• Extremal graphs for intersecting cliques
• Extremal graphs for intersecting triangles
• scientific article; zbMATH DE number 5942358 (Why is no real title available?)
• scientific article; zbMATH DE number 4200236 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• Hypergraph Turán numbers of linear cycles
• On Planar Graphical Degree Sequences
• On the structure of linear graphs
• Turán numbers for odd wheels
• Turán problems and shadows. I: Paths and cycles

Cited in

(25)

• Planar Turán numbers on short cycles of consecutive lengths
• Planar Turán number of intersecting triangles
• Planar Turán numbers of cycles: a counterexample
• Rainbow numbers for paths in planar graphs
• Rainbow numbers for small graphs in planar graphs
• Extremal Theta-free planar graphs
• Planar Turán numbers of short paths
• Extremal \(C_{4}\)-free/\(C_{5}\)-free planar graphs
• Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs
• Plane graphs with large faces and small diameter
• Planar Turán number of the 6-cycle
• On the maximum number of edges in planar graphs of bounded degree and matching number
• Extremal \(P_8\)-free/\(P_9\)-free planar graphs
• Outerplanar Turán numbers of cycles and paths
• Planar Turán numbers of cubic graphs and disjoint union of cycles
• Planar Turán number of the disjoint union of cycles
• Nonplanar Graph Drawings with k Vertices per Face
• On the rainbow planar Turán number of double stars
• The planar Turán number of _6-graphs
• The planar Turán number of double star \(S_{2,4}\)
• On the planarity of Hanoi graphs
• The planar Turán number of double stars \(S_{2,l}\)
• Planar Turán number of two adjacent cycles
• Planar Turán numbers of three configurations
• Faces in girth-saturated graphs on surfaces

This page was built for publication: Extremal \(H\)-free planar graphs

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