|
|||||
|
|
Excluding induced subgraphs: quadrilaterals |
|
| Authors: | Hans Jü Rgen Pr mel,Angelika Steger |
| Affiliation: | Hans JüRgen Prömel,Angelika Steger |
| Abstract: | In this note we determine the structure of “almost all” graphs not containing a quadrilateral (i.e., a cycle of length four) as an induced subgraph. In particular, it turns out that there are asymptotically twice as many graphs not containing an induced quadrilateral than there are bipartite graphs. |
| Keywords: | |