The Complement Problem for Linklessly Embeddable Graphs

DOI10.1142/S0218216522500754zbMATH Open1512.57036arXiv2108.12946MaRDI QIDQ6376293FDOQ6376293

Authors: Ryan Odeneal, Ramin Naimi, Andrei Pavelescu, Elena Pavelescu 

Publication date: 29 August 2021

Abstract: We find all maximal linklessly embeddable graphs of order up to 11, and verify that for every graph $G$ of order 11 either $G$ or its complement $cG$ is intrinsically linked. We give an example of a graph $G$ of order 11 such that both $G$ and $cG$ are $K_6$-minor free. We provide minimal order examples of maximal linklessly embeddable graphs that are not triangular or not 3-connected. We prove a Nordhaus-Gaddum type conjecture on the Colin de Verdi`ere invariant for graphs on at most 11 vertices. We give a description of the programs used in the search.

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Relations of low-dimensional topology with graph theory (57M15) Knot theory (57K10)

This page was built for publication: The Complement Problem for Linklessly Embeddable Graphs

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