Premium
On the structure of clique‐free graphs
Author(s) -
Prömel Hans Jürgen,
Schickinger Thomas,
Steger Angelika
Publication year - 2001
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.1017
Subject(s) - bipartite graph , combinatorics , mathematics , vertex (graph theory) , cardinality (data modeling) , complete bipartite graph , discrete mathematics , triangle free graph , clique , rothschild , chordal graph , graph , 1 planar graph , computer science , history , archaeology , data mining
Using a clever inductive counting argument Erdős, Kleitman and Rothschild showed in 1976 that almost all triangle‐free graphs are bipartite, i.e., that the cardinality of the two graph classes is asymptotically equal. In this paper we 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. We also show that similar results hold if we replace “triangle‐free” by K +1 ‐free and “bipartite” by ‐partite. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19, 37–53, 2001