The asymptotic number of graphs not containing a fixed color-critical subgraph |
| |
Authors: | H. J. Prömel A. Steger |
| |
Affiliation: | (1) Institut für Diskrete Mathematik, Universität Bonn, D-5300 Bonn, Germany |
| |
Abstract: | For a finite graphG letForb(H) denote the class of all finite graphs which do not containH as a (weak) subgraph. In this paper we characterize the class of those graphsH which have the property that almost all graphs inForb(H) are -colorable. We show that this class corresponds exactly to the class of graphs whose extremal graph is the Turán-graphTn().An earlier result of Simonovits (Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions,Discrete Math.7 (1974), 349–376) shows that these are exactly the (+1)-chromatic graphs which contain a color-critical edge. |
| |
Keywords: | 05 C 35 05 C 80 05 C 30 68 R 05 |
本文献已被 SpringerLink 等数据库收录! |