Bipartite labeling of trees with maximum degree three

C. Paul Bonnington, Jozef Širáň

Research output: Contribution to journalArticleResearchpeer-review

11 Citations (Scopus)


Let T = (V, E) be a tree with a properly 2-colored vertex set. A bipartite labeling of T is a bijection φ: V → {1, . . . , |V|} for which there exists a κ such that whenever φ(u) ≤ κ < φ(v), then u and v have different colors. The α-size α(T) of the tree T is the maximum number of elements in the sets {|φ(u) - φ(v)|; uv ∈ E}, taken over all bipartite labelings φ of T. The quantity α(n) is defined as the minimum of α(T) over all trees with n vertices. In an earlier article (J Graph Theory 19 (1995), 201 -215), A. Rosa and the second author proved that 5n/7 ≤ α(n) ≤ (5n + 4)/6 for all n ≥ 4; the upper bound is believed to be the asymptotically correct value of α(n). In this article, we investigate the αsize of trees with maximum degree three. Let α3(n) be the smallest α-size among all trees with n vertices, each of degree at most three. We prove that α3(n) ≥ 5n/6 for all n ≥ 12, thus supporting the belief above. This result can be seen as an approximation toward the graceful tree conjecture - it shows that every tree on n ≥ 12 vertices and with maximum degree three has "gracesize" at least 5n/6. Using a computer search, we also establish that α3(n) ≥ n - 2 for all n ≤ 17.

Original languageEnglish
Pages (from-to)7-15
Number of pages9
JournalJournal of Graph Theory
Issue number1
Publication statusPublished - 1 Jan 1999
Externally publishedYes


  • Bipartite labeling
  • Graceful tree conjecture

Cite this