A linear bound for the Colin de Verdiére parameter $μ$ for graphs embedded on surfaces

Camille Lanuel; Francis Lazarus; Rudi Pendavingh

doi:10.48550/arXiv.2303.00556

A linear bound for the Colin de Verdiére parameter $μ$ for graphs embedded on surfaces

Camille Lanuel
, Francis Lazarus
, Rudi Pendavingh

Combinatorial Optimization

Research output: Contribution to journal › Article › Academic

87 Downloads (Pure)

Abstract

We provide a combinatorial and self-contained proof that for all graphs $G$ embedded on a surface $S$, the Colin de Verdi\`ere parameter $\mu(G)$ is upper bounded by $7-2\chi(S)$.

Original language	English
Article number	2303.00556
Number of pages	9
Journal	arXiv
Volume	2023
DOIs	https://doi.org/10.48550/arXiv.2303.00556
Publication status	Published - 1 Mar 2023

Keywords

math.CO
cs.CG

Access to Document

10.48550/arXiv.2303.00556

2303.00556v1Final published version, 361 KB

Cite this

@article{351e2ae4c13f42ed9d2d7a8525f35c3a,

title = "A linear bound for the Colin de Verdi{\'e}re parameter \$μ\$ for graphs embedded on surfaces",

abstract = "We provide a combinatorial and self-contained proof that for all graphs \$G\$ embedded on a surface \$S\$, the Colin de Verdi\textbackslash{}`ere parameter \$\textbackslash{}mu(G)\$ is upper bounded by \$7-2\textbackslash{}chi(S)\$.",

keywords = "math.CO, cs.CG",

author = "Camille Lanuel and Francis Lazarus and Rudi Pendavingh",

year = "2023",

month = mar,

day = "1",

doi = "10.48550/arXiv.2303.00556",

language = "English",

volume = "2023",

journal = "arXiv",

issn = "2331-8422",

publisher = "Cornell University",

}

TY - JOUR

T1 - A linear bound for the Colin de Verdiére parameter $μ$ for graphs embedded on surfaces

AU - Lanuel, Camille

AU - Lazarus, Francis

AU - Pendavingh, Rudi

PY - 2023/3/1

Y1 - 2023/3/1

N2 - We provide a combinatorial and self-contained proof that for all graphs $G$ embedded on a surface $S$, the Colin de Verdi\`ere parameter $\mu(G)$ is upper bounded by $7-2\chi(S)$.

AB - We provide a combinatorial and self-contained proof that for all graphs $G$ embedded on a surface $S$, the Colin de Verdi\`ere parameter $\mu(G)$ is upper bounded by $7-2\chi(S)$.

KW - math.CO

KW - cs.CG

U2 - 10.48550/arXiv.2303.00556

DO - 10.48550/arXiv.2303.00556

M3 - Article

SN - 2331-8422

VL - 2023

JO - arXiv

JF - arXiv

M1 - 2303.00556

ER -

A linear bound for the Colin de Verdiére parameter $μ$ for graphs embedded on surfaces

Abstract

Keywords

Access to Document

Fingerprint

Cite this