Maximal Chordal Subgraphs

Abstract: A chordal graph is a graph with no induced cycles of length at least

4

. Let

f (n, m)

be the maximal integer such that every graph with

n

vertices and

m

edges has a chordal subgraph with at least

f (n, m)

edges. In 1985 ErdH{o}s and Laskar posed the problem of estimating

f (n, m)

. In the late '80s, ErdH{o}s, Gy'arf'as, Ordman and Zalcstein determined the value of

f (n, n^{2} / 4 + 1)

and made a conjecture on the value of

f (n, n^{2} / 3 + 1)

. In this paper we prove this conjecture and answer the question of ErdH{o}s and Laskar, determining

f (n, m)

asymptotically for all

m

and exactly for

m l e q n^{2} / 3 + 1

.

This page was built for publication: Maximal Chordal Subgraphs