Geodesic
The extremal function and Colin de Verdière graph parameter
Rose McCarty1
1Georgia Institute of Technology
The electronic journal of combinatorics, Tome 25 (2018) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

The Colin de Verdière parameter $\mu(G)$ is a minor-monotone graph parameter with connections to differential geometry. We study the conjecture that for every integer $t$, if $G$ is a graph with at least $t$ vertices and $\mu(G) \leq t$, then $|E(G)| \leq t|V(G)|-\binom{t+1}{2}$. We observe a relation to the graph complement conjecture for the Colin de Verdière parameter and prove the conjectured edge upper bound for graphs $G$ such that either $\mu(G) \leq 7$, or $\mu(G) \geq |V(G)|-6$, or the complement of $G$ is chordal, or $G$ is chordal.
DOI : 10.37236/7195
Classification : 05C35, 05C38, 05C10, 05C50
Mots-clés : graph theory, planar graphs, graph parameters, Colin de Verdière parameter, extremal graph theory, extremal function, graph complements, chordal graphs, graph minors

Rose McCarty  1

1 Georgia Institute of Technology 
@article{10_37236_7195,
     author = {Rose McCarty},
     title = {The extremal function and {Colin} de {Verdi\`ere} graph parameter},
     journal = {The electronic journal of combinatorics},
     year = {2018},
     volume = {25},
     number = {2},
     doi = {10.37236/7195},
     zbl = {1391.05140},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/7195/}
}
TY  - JOUR
AU  - Rose McCarty
TI  - The extremal function and Colin de Verdière graph parameter
JO  - The electronic journal of combinatorics
PY  - 2018
VL  - 25
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/7195/
DO  - 10.37236/7195
ID  - 10_37236_7195
ER  - 
%0 Journal Article
%A Rose McCarty
%T The extremal function and Colin de Verdière graph parameter
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/7195/
%R 10.37236/7195
%F 10_37236_7195
Rose McCarty. The extremal function and Colin de Verdière graph parameter. The electronic journal of combinatorics, Tome 25 (2018) no. 2. doi: 10.37236/7195

Cité par Sources :