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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.