论文标题
最大和弦子图
Maximal Chordal Subgraphs
论文作者
论文摘要
和弦图是一个没有诱导的循环至少$ 4 $的图形。令$ f（n，m）$为最大整数，以使每个具有$ n $顶点和$ m $ edges的图形具有至少$ f（n，m）$边缘的和弦子图。 1985年，ErdőS和Laskar提出了估计$ F（N，M）$的问题。在80年代后期，Erdős，Gyárfás，Ordman和Zalcstein确定了$ f（n，n^2/4+1）$的值，并猜想了$ f（n，n^2/3+1）$的值。在本文中，我们证明了这个猜想，并回答了Erdős和Laskar的问题，对所有$ m $ y nake $ f（n，m）$渐近，正是$ m \ m \ leq n^2/3+1 $。
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 Erdős and Laskar posed the problem of estimating $f(n,m)$. In the late '80s, Erdős, Gyárfás, 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 Erdős and Laskar, determining $f(n,m)$ asymptotically for all $m$ and exactly for $m \leq n^2/3+1$.
