solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看199次
The Extremal Function and Colin de Verdi\`{e}re Graph Parameter. (arXiv:1706.07451v1 [math.CO])
来源于:arXiv
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 $|E(G)| \leq t|V(G)|-\binom{t+1}{2}$. 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) \leq 7$, or $\mu(G) \geq |V(G)|-6$, or the complement of $G$ is
chordal, or $G$ is chordal. 查看全文>>