The extremal function and Colin de Verdière graph parameter

zbMATH Open1391.05140arXiv1706.07451MaRDI QIDQ1753124FDOQ1753124

Rose McCarty

Publication date: 25 May 2018

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We study the maximum number of edges in an $n$ vertex graph with Colin de Verdi`{e}re parameter no more than $t$. We conjecture that for every integer $t$, if $G$ is a graph with at least $t$ vertices and Colin de Verdi`{e}re parameter at most $t$, then $$. We observe a relation to the graph complement conjecture for the Colin de Verdi`{e}re parameter and prove the conjectured edge upper bound for graphs $G$ such that either $mu(G)leq7$, or $mu(G)geq|V(G)|-6$, or the complement of $G$ is chordal, or $G$ is chordal.

Full work available at URL: https://arxiv.org/abs/1706.07451

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

graph theoryextremal functionextremal graph theorychordal graphsgraph minorsplanar graphsgraph parametersgraph complementsColin de Verdière parameter

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Zero forcing sets and the minimum rank of graphs
• Hadwiger's conjecture is true for almost every graph
• The extremal function for \(K_{9}\) minors
• Homomorphiesätze für Graphen
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Hadwiger’s Conjecture
• An extremal function for contractions of graphs
• Contractions to k₈
• Lower bound of the Hadwiger number of graphs by their average degree
• The four-colour theorem
• Every Planar Map is Four Colorable
• The Colin de Verdière number and sphere representations of a graph
• Parameters Related to Tree‐Width, Zero Forcing, and Maximum Nullity of a Graph
• Sphere representations, stacked polytopes, and the Colin de Verdière number of a graph
• Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion)
• Sachs' linkless embedding conjecture
• On the graph complement conjecture for minimum rank
• A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs
• Three-connected graphs whose maximum nullity is at most three
• On the relation between two minor-monotone graph parameters
• Expected values of parameters associated with the minimum rank of a graph
• Throttling zero forcing propagation speed on graphs
• On the invariance of Colin de Verdière's graph parameter under clique sums
• Colin de Verdiere parameters of chordal graphs
• On embeddability and stresses of graphs
• The extremal functions for triangle-free graphs with excluded minors
• Nordhaus-Gaddum problems for Colin de Verdière type parameters, variants of tree-width, and related parameters

Cited In (3)

• The extremal function for 3-linked graphs
• The Colin de Verdière number and sphere representations of a graph
• The Colin de Verdière number and joins of graphs

This page was built for publication: The extremal function and Colin de Verdière graph parameter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1753124)