𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The vertex separation number of a graph equals its path-width

✍ Scribed by Nancy G. Kinnersley

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
497 KB
Volume
42
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the separation number of a graph
On the separation number of a graph
✍ Zevi Miller; Dan Pritikin πŸ“‚ Article πŸ“… 1989 πŸ› John Wiley and Sons 🌐 English βš– 781 KB

We consider the following graph labeling problem, introduced by Leung et al. (3. Y-T. Leung, 0. Vornberger, and J. D. Witthoff, On some variants of the bandwidth minimization problem. SIAM J. Comput. 13 (1984) 650-667). Let G be a graph of order n, and f a bijection from the separation number of G,

An upper bound for the path number of a
An upper bound for the path number of a graph
✍ Alan Donald πŸ“‚ Article πŸ“… 1980 πŸ› John Wiley and Sons 🌐 English βš– 529 KB

## Abstract The path number of a graph __G__, denoted __p(G)__, is the minimum number of edge‐disjoint paths covering the edges of __G.__ LovΓ‘sz has proved that if __G__ has __u__ odd vertices and __g__ even vertices, then __p(G)__ ≀ 1/2 __u__ + __g__ ‐ 1 ≀ __n__ ‐ 1, where __n__ is the total numbe

On the equality of the grundy and ochrom
On the equality of the grundy and ochromatic numbers of a graph
✍ P. ErdΓΆs; W. R. Hare; S. T. Hedetniemi; R. Laskar πŸ“‚ Article πŸ“… 1987 πŸ› John Wiley and Sons 🌐 English βš– 162 KB πŸ‘ 1 views

It is proved in this note that the Grundy number, r(G), and the ochromatic number, xo(G), are the same for any graph G. An n-coloring of a graph G = ( V , E ) is a f u n c t i o n f f r o m V onto N = { I , 2 , . . . , n } such that, whenever vertices id and u are adjacent, then f ( u ) f f(u). An

Some new bounds for the maximum number o
Some new bounds for the maximum number of vertex colorings of a (v,e)-graph
✍ Byer, Owen D. πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 126 KB πŸ‘ 3 views

Let f (v, e, Ξ») denote the maximum number of proper vertex colorings of a graph with v vertices and e edges in Ξ» colors. In this paper we present some new upper bounds for f (v, e, Ξ»). In particular, a new notion of pseudoproper colorings of a graph is given, which allows us to significantly improve

The minimum number of subgraphs in a gra
The minimum number of subgraphs in a graph and its complement
✍ Lane Clark πŸ“‚ Article πŸ“… 1992 πŸ› John Wiley and Sons 🌐 English βš– 265 KB πŸ‘ 2 views

## Abstract For a graphb __F__ without isolated vertices, let __M__(__F__; __n__) denote the minimum number of monochromatic copies of __F__ in any 2‐coloring of the edges of __K__~__n__~. Burr and Rosta conjectured that when __F__ has order __t__, size __u__, and __a__ automorphisms. Independent