The extremal function for bipartite linklessly embeddable graphs

DOI10.1007/S00493-019-3856-ZMaRDI QIDQ2288359zbMATH OpenOpenAlexWikidataFDO

Authors Rose McCarty, Robin Thomas

Publication date 17 January 2020

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

bipartite graphslinkless embedding

Mathematics Subject Classification ID

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

Abstract: An embedding of a graph in $3$-space is linkless if for every two disjoint cycles there exists an embedded ball that contains one of the cycles and is disjoint from the other. We prove that every bipartite linklessly embeddable (simple) graph on $nge5$ vertices has at most $3n-10$ edges, unless it is isomorphic to the complete bipartite graph $K_{3,n-3}$.

Review text

In this present paper, the authors study the extremal problem of finding the maximum number of edges in a bipartite linklessly embeddable graph having \(n\) vertices.\par An embedding of a graph in \(\mathbb{R}^3\) is linkless if for every two disjoint cycles there exists an embedded ball that contains one of the cycles and is disjoint from the other. In the present paper, the authors prove that every bipartite linklessly embeddable (simple) graph on \(n \geq 5\) vertices has at most \(3n-10\) edges, unless it is isomorphic to the complete bipartite graph \(K_{3,n-3}\).

Recommendations

• On the number of edges in maximally linkless graphs
• ON THE SIZE OF LINKS IN K_{n, n}, K_{n, n, 1}, AND K_n
• INTRINSICALLY n-LINKED COMPLETE BIPARTITE GRAPHS
• The complement problem for linklessly embeddable graphs
• The extremal function for 3-linked graphs

Cited in

(6)

• An infinite family of linklessly embeddable Tutte-4-connected graphs
• scientific article; zbMATH DE number 4139789 (Why is no real title available?)
• A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs
• On the number of edges in maximally linkless graphs
• New bounds on maximal linkless graphs
• The extremal function for 3-linked graphs

This page was built for publication: The extremal function for bipartite linklessly embeddable graphs

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