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. Erdos, we prove that, if the minimum degree of G is at least 9 vertical bar V(G)vertical bar/10, 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.
| Original language | English |
|---|---|
| Journal | Combinatorica |
| Volume | 26 |
| Issue number | 2 |
| Pages (from-to) | 121-131 |
| ISSN | 0209-9683 |
| DOIs | |
| Publication status | Published - 2006 |
Fingerprint
Dive into the research topics of 'Density conditions for triangles in multipartite graphs'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver