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

2023/03/01 by Camille Lanuel, Lanuel, Camille, Francis Lazarus +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Geometric and Algebraic Topology #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.2303.00556

openalex publication_date 2023/03/01 · openalex created_date 2023/03/03 · openalex updated_date 2026/07/28

Abstract

We provide a combinatorial and self-contained proof that for all graphs G embedded on a surface S, the Colin de Verdière parameter μ(G) is upper bounded by 7-2χ(S).

Related

• Three observations on the Colin de Verdière spectral graph parameter
• On the Colin de Verdiere graph number and penny graphs
• The Colin de Verdière number and graphs of polytopes
• The Colin de Verdière Graph Parameter for Threshold Graphs
• On the surface area of graphs, related connectivity measures and spectral estimates