Density conditions for triangles in multipartite graphs

Adrian Bondy, Jin Shen, Stephan Thomassé, Carsten Thomassen

    Research output: Contribution to journalJournal articleResearchpeer-review

    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 languageEnglish
    JournalCombinatorica
    Volume26
    Issue number2
    Pages (from-to)121-131
    ISSN0209-9683
    DOIs
    Publication statusPublished - 2006

    Fingerprint Dive into the research topics of 'Density conditions for triangles in multipartite graphs'. Together they form a unique fingerprint.

    Cite this