| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 5777581 | Journal of Combinatorial Theory, Series B | 2017 | 12 Pages |
Abstract
A connection between the acyclic coloring and the existence of universal graphs was first observed by Alon and Marshall (1998) [2]. One of their results is that for the class of planar graphs, the size of the smallest k-universal graph is between k3+3 and 5k4. Our results yield that there exists a constant c such that for all k, this size is bounded from above by ck3.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Grzegorz GuÅpiel, Grzegorz Gutowski,