High girth augmented trees are huge

Research output: Contribution to journalArticlepeer-review


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 [2], 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.

Original languageEnglish (US)
Pages (from-to)7-15
Number of pages9
JournalJournal of Combinatorial Theory. Series A
StatePublished - Nov 1 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


  • Ackermann Hierarchy
  • Chromatic number
  • High girth


Dive into the research topics of 'High girth augmented trees are huge'. Together they form a unique fingerprint.

Cite this