Back to Search
Start Over
Excluding induced subgraphs: quadrilaterals
- Source :
- Random Structures & Algorithms. 2:55-71
- Publication Year :
- 1991
- Publisher :
- Wiley, 1991.
-
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.
Details
- ISSN :
- 10429832
- Volume :
- 2
- Database :
- OpenAIRE
- Journal :
- Random Structures & Algorithms
- Accession number :
- edsair.doi...........1d5480a32e24b7a48152f593cc73919d
- Full Text :
- https://doi.org/10.1002/rsa.3240020106