# Density Conditions for Triangles in Multipartite Graphs

3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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$.
Type de document :
Article dans une revue

Littérature citée [3 références]

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00140328
Contributeur : Stephan Thomasse <>
Soumis le : lundi 11 juin 2007 - 10:54:13
Dernière modification le : mardi 20 mars 2018 - 11:40:02
Document(s) archivé(s) le : mercredi 7 avril 2010 - 03:11:20

### Citation

Adrian Bondy, Jian Shen, Stéphan Thomassé, Carsten Thomassen. Density Conditions for Triangles in Multipartite Graphs. Combinatorica, Springer Verlag, 2006, 26, pp.121-131. 〈http://www.lirmm.fr/~thomasse/liste/triangle.pdf〉. 〈10.1007/s00493-006-0009-y〉. 〈lirmm-00140328〉

### Métriques

Consultations de la notice

## 145

Téléchargements de fichiers