Let G be a graph consisting of a complete binary tree of depth h together with one back edge leading from each leaf to one of its ancestors, and suppose that the girth of G exceeds g. Let h=h(g) be the minimum possible depth of such a graph. The existence of such graphs, for arbitrarily large g, is proved in , where it is shown that h(g) is at most some version of the Ackermann function. Here we show that this is tight and the growth of h(g) is indeed Ackermannian.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Ackermann Hierarchy
- Chromatic number
- High girth