Maximal chordal subgraphs
OPEN ACCESS
Loading...
Author / Producer
Date
2023-09
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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 Erdos and Laskar posed the problem of estimating f (n, m). In the late 1980s, Erdos, Gyarfas, Ordman and Zalcstein determined the value of f (n, n(2)/4 + 1) and made a conjecture on the value off (n, n(2)/3 + 1). In this paper we prove this conjecture and answer the question of Erdos and Laskar, determining f(n, m) asymptotically for all m and exactly for m = n(2)/3 + 1.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
32 (5)
Pages / Article No.
724 - 741
Publisher
Cambridge University Press
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
chordal subgraph
Organisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin
Notes
Funding
196965 - Problems in Extremal and Probabilistic Combinatorics (SNF)