𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The achromatic number of bounded degree trees

✍ Scribed by Niall Cairnie; Keith Edwards

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
621 KB
Volume
188
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

The achromatic number ~b(G) of a simple graph G is the largest number of colours possible in a proper vertex colouring of G in which each pair of coiours appears on at least one edge.

The problem of determining the achromatic number of a tree is known to be NP-hard (Cairnie and Edwards, 1997). In this paper, we present a polynomial-time algorithm for determining the achromatic number of a tree with maximum degree at most d, where d is a fixed positive integer.

Prior to giving this algorithm, we show that there is a natural number N(d) such that if T is any tree with m>~N(d) edges, and maximum degree at most d, then ~(T) is k or k -1, where k is the largest integer such that (k2)~<m. (~

πŸ“œ SIMILAR VOLUMES

The 2-intersection number of paths and b
The 2-intersection number of paths and bounded-degree trees
✍ Michael S. Jacobson; AndrΓ© E. KΓ©zdy; Douglas B. West πŸ“‚ Article πŸ“… 1995 πŸ› John Wiley and Sons 🌐 English βš– 416 KB πŸ‘ 1 views

## Abstract We represent a graph by assigning each vertex a finite set such that vertices are adjacent if and only if the corresponding sets have at least two common elements. The __2‐intersection number__ ΞΈ~2~(__G__) of a graph __G__ is the minimum size of the union of sets in such a representatio

Maximizing the number of independent sub
Maximizing the number of independent subsets over trees with bounded degree
✍ Clemens Heuberger; Stephan G Wagner πŸ“‚ Article πŸ“… 2008 πŸ› John Wiley and Sons 🌐 English βš– 208 KB πŸ‘ 1 views

## Abstract The number of independent vertex subsets is a graph parameter that is, apart from its purely mathematical importance, of interest in mathematical chemistry. In particular, the problem of maximizing or minimizing the number of independent vertex subsets within a given class of graphs has

On the Achromatic Number of Hypercubes
On the Achromatic Number of Hypercubes
✍ Yuval Roichman πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 96 KB

The achromatic number of a finite graph G, (G), is the maximum number of independent sets into which the vertex set may be partitioned, so that between any two parts there is at least one edge. For an m-dimensional hypercube P m 2 we prove that there exist constants 0<c 1 <c 2 , independent of m, su