1999/05/01 by Stephan Brandt · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Corollary #Discrete mathematics #Epigraph #Graph #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Line graph #Mathematics #Petersen graph #Vertex (graph theory) #Voltage graph
paper · doi:10.1017/s0963548399003831
openalex publication_date 1999/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21
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.