The extremal function and Colin de Verdière graph parameter

MaRDI QIDQ1753124zbMATH OpenFDO

Authors Rose McCarty

Publication date 25 May 2018

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

Full work available at URL https://arxiv.org/abs/1706.07451, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p32

IPFS 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)

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.

Recommendations

• On the Colin de Verdière number of graphs
• scientific article; zbMATH DE number 1303522
• Colin de Verdière parameters of chordal graphs
• On Vertex Partitions and the Colin de Verdière Parameter
• On the relation between two minor-monotone graph parameters

Cites work

• scientific article; zbMATH DE number 1303522 (Why is no real title available?)
• scientific article; zbMATH DE number 475582 (Why is no real title available?)
• scientific article; zbMATH DE number 475583 (Why is no real title available?)
• A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs
• An extremal function for contractions of graphs
• Colin de Verdière parameters of chordal graphs
• Contractions to k₈
• Every Planar Map is Four Colorable
• Expected values of parameters associated with the minimum rank of a graph
• Hadwiger's conjecture
• Hadwiger's conjecture is true for almost every graph
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Homomorphiesätze für Graphen
• Lower bound of the Hadwiger number of graphs by their average degree
• Nordhaus-Gaddum problems for Colin de Verdière type parameters, variants of tree-width, and related parameters
• On embeddability and stresses of graphs
• On the graph complement conjecture for minimum rank
• On the invariance of Colin de Verdière's graph parameter under clique sums
• On the relation between two minor-monotone graph parameters
• Parameters related to tree-width, zero forcing, and maximum nullity of a graph
• Sachs' linkless embedding conjecture
• 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)
• The Colin de Verdière number and sphere representations of a graph
• The extremal function for \(K_{9}\) minors
• The extremal functions for triangle-free graphs with excluded minors
• The four-colour theorem
• Three-connected graphs whose maximum nullity is at most three
• Throttling zero forcing propagation speed on graphs
• Zero forcing sets and the minimum rank of graphs

Cited in

(6)

• A linear bound for the Colin de Verdière parameter \(\mu\) for graphs embedded on surfaces
• The extremal function for 3-linked graphs
• The Colin de Verdière number and sphere representations of a graph
• On Vertex Partitions and the Colin de Verdière Parameter
• The Colin de Verdière number and joins of graphs
• Colin de Verdière parameters of chordal 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)