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

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic

51 Downloads (Pure)

Samenvatting

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)$.

Originele taal-2	Engels
Artikelnummer	2303.00556
Aantal pagina's	9
Tijdschrift	arXiv
Volume	2023
DOI's	https://doi.org/10.48550/arXiv.2303.00556
Status	Gepubliceerd - 1 mrt. 2023

Toegang tot document

10.48550/arXiv.2303.00556

2303.00556v1Definitieve gepubliceerde versie, 361 KB

Citeer dit

@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\`ere parameter $\mu(G)$ is upper bounded by $7-2\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 Library",

}

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

Samenvatting

Toegang tot document

Vingerafdruk

Citeer dit