The Generation of Maximal Triangle-Free Graphs

被引：0

作者：

Stephan Brandt

Gunnar Brinkmann

Thomas Harmuth

机构：

[1] FB Mathematik,

[2] Freie Universität Berlin,undefined

[3] D 14195 Berlin,undefined

[4] Germany e-mail: brandt@math.fu-berlin.de,undefined

[5] Fakultät für Mathematik,undefined

[6] Universität Bielefeld,undefined

[7] D 33501 Bielefeld,undefined

[8] Germany e-mail: gunnar@mathematik.uni-bielefeld.de,undefined

[9] FSP Mathematisierung,undefined

[10] Universität Bielefeld,undefined

[11] D 33501 Bielefeld,undefined

[12] Germany e-mail: harmuth@mathematik.uni-bielefeld.de,undefined

来源：

Graphs and Combinatorics | 2000年 / 16卷 / 2期

关键词：

Local Density; Efficient Algorithm; Ramsey Number;

D O I：

10.1007/PL00021176

中图分类号：

学科分类号：

摘要：

In this paper we present an efficient algorithm for generating maximal triangle-free graphs. A program based on this algorithm has been used to check a conjecture of Erdo´´s about the local density of triangle-free graphs and turned out to be very powerful for the computation of triangle Ramsey numbers.

引用

页码：149 / 157

页数：8