##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 626.05045

**Autor: ** Erdös, Paul; Ordman, Edward T.; Zalcstein, Yechezkel

**Title: ** Bounds on threshold dimension and disjoint threshold coverings. (In English)

**Source: ** SIAM J. Algebraic Discrete Methods 8, 151-154 (1987).

**Review: ** The threshold dimension (threshold covering number) of a graph G is the least number of threshold graphs needed to edgecover the graph G. If tc(n) is the greatest threshold dimension of any graph of n vertices, we show that for some constant A, n-A\sqrt{n} log n < tc(n) < n-\sqrt{n}+1. We establish the same bounds for edge-disjoint coverings of graphs by threshold graphs (threshold partitions). We give an example to show there exist planar graphs on n vertices with a smallest covering of An threshold graphs and a smallest partition of Bn threshold graphs, with B = 1.5A. Thus the difference between these two covering numbers can grow linearly in the number of vertices.

**Classif.: ** * 05C70 Factorization, etc.

**Keywords: ** graph partition; threshold dimension; threshold covering number; threshold graphs; coverings; threshold partitions

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag