Density Conditions for Triangles in Multipartite Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Combinatorica Année : 2006

Density Conditions for Triangles in Multipartite Graphs

Résumé

We consider the problem of finding a large or dense triangle-free subgraph in a given graph $G$. In response to a question of P. Erd\H{o}s, we prove that, if the minimum degree of $G$ is at least $17|V(G)|/20 $, the largest triangle-free subgraphs are precisely the largest bipartite subgraphs in $G$. We investigate in particular the case where $G$ is a complete multipartite graph. We prove that a finite tripartite graph with all edge densities greater than the golden ratio has a triangle and that this bound is best possible. Also we show that an infinite-partite graph with finite parts has a triangle, provided that the edge density between any two parts is greater than $1/2$.
Fichier principal
Vignette du fichier
triangle.pdf (131.45 Ko) Télécharger le fichier
Loading...

Dates et versions

lirmm-00140328 , version 1 (11-06-2007)

Identifiants

Citer

Adrian Bondy, Jian Shen, Stéphan Thomassé, Carsten Thomassen. Density Conditions for Triangles in Multipartite Graphs. Combinatorica, 2006, 26, pp.121-131. ⟨10.1007/s00493-006-0009-y⟩. ⟨lirmm-00140328⟩
136 Consultations
509 Téléchargements

Altmetric

Partager

More