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) = [n2/4]+1. Further, we prove that any G(n,[n2/4]+1) contains a chordal subgraph of size n(1+\epsilon) if n > n0(\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