Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4657438 | Journal of Combinatorial Theory, Series B | 2007 | 41 Pages |
Abstract
We show that the problem of the existence of universal graphs with specified forbidden subgraphs can be systematically reduced to certain critical cases by a simple pruning technique which simplifies the underlying structure of the forbidden graphs, viewed as trees of blocks. As an application, we characterize the trees T for which a universal countable T-free graph exists.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics