The Complement Problem for Linklessly Embeddable Graphs
| Autor: | Ryan Odeneal, Ramin Naimi, Andrei Pavelescu, Elena Pavelescu |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: | |
| Popis: | 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. Comment: 10 pages, 5 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|