A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs
A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs
复制标题
对映链接的 Borsuk 定理和无链接嵌入图的谱表征
DOI：
10.1090/s0002-9939-98-04244-0
复制
发表时间：
1998
影响因子：
0.9
通讯作者：
A. Schrijver
中科院分区：
文献类型：
--
作者：
L. Lovász;A. Schrijver
对任意无向图G，设μ（G）为Colin de Verdiere引入的图参数.本文证明了μ（G）≤ 4当且仅当G是无链可嵌入的（在R中）.这形成了无链可嵌入图的谱特征，并由Robertson，Seymour和托马斯证明。一个关键的组成部分是关于在某些映射φ：S → R中存在一对映连通（k− 1）球面的Borsuk型定理。这一结果本身可能是令人感兴趣的。对于任意的无链可嵌入图G =（V，E），λ（G）≤ 4，其中λ（G）是由货车der Holst，Laurent和Schrijver引入的图参数. (It是R的任意子空间L的最大维数，使得对于每个非零x ∈ L，x的正支撑诱导G的非空连通子图。）
For any undirected graph G, let μ(G) be the graph parameter introduced by Colin de Verdiere. In this paper we show that μ(G) ≤ 4 if and only if G is linklessly embeddable (in R). This forms a spectral characterization of linklessly embeddable graphs, and was conjectured by Robertson, Seymour, and Thomas. A key ingredient is a Borsuk-type theorem on the existence of a pair of antipodal linked (k− 1)spheres in certain mappings φ : S → R. This result might be of interest in its own right. We also derive that λ(G) ≤ 4 for each linklessly embeddable graph G = (V,E), where λ(G) is the graph paramer introduced by van der Holst, Laurent, and Schrijver. (It is the largest dimension of any subspace L of R such that for each nonzero x ∈ L, the positive support of x induces a nonempty connected subgraph of G.)