In:
Combinatorics, Probability and Computing, Cambridge University Press (CUP), Vol. 8, No. 3 ( 1999-05), p. 237-245
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 C 5 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 of Medium:
Online Resource
ISSN:
0963-5483
,
1469-2163
DOI:
10.1017/S0963548399003831
Language:
English
Publisher:
Cambridge University Press (CUP)
Publication Date:
1999
detail.hit.zdb_id:
1481145-5
SSG:
17,1
