On the structure of clique-free graphs (Q2748425)

It is known that almost all triangle-free graphs are bipartite, i.e., that the cardinalities of the two graph classes are asymptotically equal. In this paper the authors investigate the structure of the ``few'' triangle-free graphs which are not bipartite. As it turns out, with high probability, these graphs are bipartite up to a few vertices. More precisely, almost all of them can be made bipartite by removing just one vertex. Almost all others can be made bipartite by removing two vertices, and then three vertices, and so on. The authors also show that similar results hold if one replaces ``triangle-free'' by \(K_{l+1}\)-free and bipartite by \(l\)-partite.