4
$\begingroup$

Let $G$ be an $n$-vertex chordal graph and let $\omega(G)$ be the clique number of $G$.

The fact that $G$ admits a perfect elimination ordering implies that $G$ is $\omega(G)$-degenerate.

In turn from $\omega(G)$-degeneracy of $G$ it is easy to show that for a given natural number $k$ there exists $\epsilon(k)$ such that $G$ has at least $\epsilon(k)n$ vertices of degree at most $k \omega(G)$. In other words, there are linearly many vertices of degree at most $k$ times the ‘global’ clique number. I’m wondering if ‘global’ can be replaced by ‘local’.

Formally, is the following true?

For a given natural $k$ there exists a positive number $\epsilon(k)$ such that any $n$-vertex chordal graph contains at least $\epsilon(k) n$ vertices $v$ such that $\deg(v) \leq k \omega(G[N(v)])$, where $G[N(v)]$ is the subgraph of $G$ induced by the neighbourhood of $v$.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.