3
$\begingroup$

Recall that a graph is called $k$-chordal if any cycle $C$ of length $> k$ contains a chord, i.e. an edge joining to non-consecutive vertices in $C$. Let $f(n, k)$ be the minimal number of edges s.t. any graph on $n$ vertices can be made $k$-chordal by deleting at most $f(n, k)$ edges.

There is a paper of Erd\H{o}s and Laskar "On maxinal chordal subgraph" where they show that $$ f(n,3) = \frac{n^2}{2} - (1+o(1))\sqrt{2}n^{3/2}. $$

I am wondering if other bounds for $f(n, k)$ are known for bigger $k$. A bound in terms of the number of edges is also of interest. In particular, is is true that there is some bounded $k$ s.t. $$ f(n, k) = o(|E|), $$ where $E$ is the number of edges?

UPD
The answer for the last question is NO, as seen from the following example. Take $k+1$ copies of $K_{n/(k+1)}$, call it $G_0, ..., G_k$. Join all vertices in $G_i$ and $G_{i+1}$ (addition mod $(k+1)$). One can show that for this graph $f(n, k) \geq n^2/4(k+1)^2$. It is interesting to see what is the right constant, though.

$\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.