##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 647.05034

**Autor: ** Erdös, Paul; Laskar, Renu

**Title: ** A note on the size of a chordal subgraph. (In English)

**Source: ** Combinatorics, graph theory and computing, Proc. 16th Southeast. Conf., Boca Raton/Fla. 1985, Congr. Numerantium 48, 81-86 (1985).

**Review: ** [For the entire collection see Zbl 619.00006.]

``If a graph is not chordal, it is quite appropriate to ask the following questions: (1) What is the maximum order of a chordal subgraph? (2) What is the maximum size of a chordal subgraph?

This paper is a first attempt to answer question (2). Let f(n,t) denote the smallest positive integer for which every graph G(n,f(n,t)) contains a chordal subgraph of size at least t. We show here that f(n,n) = [n^{2}/4]+1. Further, we prove that any G(n,[n^{2}/4]+1) contains a chordal subgraph of size n(1+\epsilon) if n > n_{0}(\epsilon), where \epsilon > 0 is a fixed positive number. At present we cannot determine the exact value of \epsilon. In fact, in such a graph we show the existence of a triangle xyz, with deg x+\deg y+\deg z > n(1+\eta) for small \eta > 0, such that the triangle xyz together with the incident edges of x,y,z gives such a chordal subgraph.''

**Classif.: ** * 05C38 Paths and cycles

05C35 Extremal problems (graph theory)

**Keywords: ** chordal subgraph

**Citations: ** Zbl 619.00006

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag