High girth augmented trees are huge

Research output: Contribution to journalArticle

Abstract

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
Volume144
DOIs
StatePublished - Nov 1 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Keywords

  • Ackermann Hierarchy
  • Chromatic number
  • High girth

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

  • Cite this