Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-25T12:48:50.396Z Has data issue: false hasContentIssue false

On the Structure of Dense Triangle-Free Graphs

Published online by Cambridge University Press:  01 May 1999

STEPHAN BRANDT
Affiliation:
FB Mathematik & Informatik, WE 2, Freie Universität Berlin, Arnimallee 3, 14195 Berlin, Germany (e-mail: [email protected])

Abstract

As a consequence of an early result of Pach we show that every maximal triangle-free graph is either homomorphic with a member of a specific infinite sequence of graphs or contains the Petersen graph minus one vertex as a subgraph. From this result and further structural observations we derive that, if a (not necessarily maximal) triangle-free graph of order n has minimum degree δ[ges ]n/3, then the graph is either homomorphic with a member of the indicated family or contains the Petersen graph with one edge contracted. As a corollary we get a recent result due to Chen, Jin and Koh. Finally, we show that every triangle-free graph with δ>n/3 is either homomorphic with C5 or contains the Möbius ladder. A major tool is the observation that every triangle-free graph with δ[ges ]n/3 has a unique maximal triangle-free supergraph.

Type
Research Article
Copyright
1999 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)