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

Camille Lanuel; Francis Lazarus; Rudi Pendavingh

doi:10.1137/23M1623628

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

Camille Lanuel, Francis Lazarus (Corresponding author), Rudi Pendavingh

Combinatorial Optimization

Research output: Contribution to journal › Article › Academic › peer-review

2 Downloads (Pure)

Abstract

We provide a combinatorial and self-contained proof of a result following from G. Besson [Ann. Inst. Fourier, 30 (1980), pp. 109-128] and Y. Colin de Verdiere [Ann. Sci. Ec. Norm. Super., 20 (1987), pp. 599-615] that for all graphs G embedded on a surface S, the Colin de Verdiere parameter μG is upper bounded by 7 2\chi (S).

Original language	English
Pages (from-to)	2289-2296
Number of pages	8
Journal	SIAM Journal on Discrete Mathematics
Volume	38
Issue number	3
DOIs	https://doi.org/10.1137/23M1623628
Publication status	Published - 30 Sept 2024

Bibliographical note

Publisher Copyright:
© 2024 Society for industrial and applied mathematics.

Keywords

Graph on surfaces
Graph parameter
Spectral graph theory

Access to Document

10.1137/23M1623628

pdfFinal published version, 337 KBLicence: TAVERNE

Cite this

@article{055151d001574722af87d8b0c4f62d6a,

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 of a result following from G. Besson [Ann. Inst. Fourier, 30 (1980), pp. 109-128] and Y. Colin de Verdiere [Ann. Sci. Ec. Norm. Super., 20 (1987), pp. 599-615] that for all graphs G embedded on a surface S, the Colin de Verdiere parameter μG is upper bounded by 7 2\chi (S).",

keywords = "Graph on surfaces, Graph parameter, Spectral graph theory",

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

note = "Publisher Copyright: {\textcopyright} 2024 Society for industrial and applied mathematics.",

year = "2024",

month = sep,

day = "30",

doi = "10.1137/23M1623628",

language = "English",

volume = "38",

pages = "2289--2296",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics (SIAM)",

number = "3",

}

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 - 2024/9/30

Y1 - 2024/9/30

N2 - We provide a combinatorial and self-contained proof of a result following from G. Besson [Ann. Inst. Fourier, 30 (1980), pp. 109-128] and Y. Colin de Verdiere [Ann. Sci. Ec. Norm. Super., 20 (1987), pp. 599-615] that for all graphs G embedded on a surface S, the Colin de Verdiere parameter μG is upper bounded by 7 2\chi (S).

AB - We provide a combinatorial and self-contained proof of a result following from G. Besson [Ann. Inst. Fourier, 30 (1980), pp. 109-128] and Y. Colin de Verdiere [Ann. Sci. Ec. Norm. Super., 20 (1987), pp. 599-615] that for all graphs G embedded on a surface S, the Colin de Verdiere parameter μG is upper bounded by 7 2\chi (S).

KW - Graph on surfaces

KW - Graph parameter

KW - Spectral graph theory

UR - http://www.scopus.com/inward/record.url?scp=85202153827&partnerID=8YFLogxK

U2 - 10.1137/23M1623628

DO - 10.1137/23M1623628

M3 - Article

AN - SCOPUS:85202153827

SN - 0895-4801

VL - 38

SP - 2289

EP - 2296

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 3

ER -

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

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Cite this