𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On vertex k-partitions of certain infinite graphs

✍ Scribed by Douglas Cenzer; Edward Howorka

Publisher
Elsevier Science
Year
1978
Tongue
English
Weight
826 KB
Volume
23
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be an infinite graph; define de& G to be the least m such that any partition P of the vertex set of G into sets of uniformly bounded cardinality contains a set which is adjacent to at least m Other sets of the partition. If G is either a regular tree 01 a triangtiisr, sqzart or hexagonal planar mosaic graph, it is shown that deg, G equals the degree of G. This verifies some conjectures of S. Ulam. Several open problems are given.

πŸ“œ SIMILAR VOLUMES

Note on vertex-partitions of infinite gr
Note on vertex-partitions of infinite graphs
✍ JΓ‘nos Pach; Joel H. Spencer πŸ“‚ Article πŸ“… 1990 πŸ› Elsevier Science 🌐 English βš– 118 KB

Given an infinite graph G, let deg,(G) be defined as the smallest d for which V(G) can be partitioned into finite subsets of (uniformly) bounded size such that each part is adjacent to at most d others. A countable graph G is constructed with de&(G) > 2 and with the property that [{y~V(G):d(x, y)sn}

Vertex partitions of chordal graphs
Vertex partitions of chordal graphs
✍ David R. Wood πŸ“‚ Article πŸ“… 2006 πŸ› John Wiley and Sons 🌐 English βš– 103 KB

## Abstract A __k‐tree__ is a chordal graph with no (__k__ + 2)‐clique. An ℓ‐__tree‐partition__ of a graph __G__ is a vertex partition of __G__ into β€˜bags,’ such that contracting each bag to a single vertex gives an ℓ‐tree (after deleting loops and replacing parallel edges by a single edge). We pro

On vertex partitions and some minor-mono
On vertex partitions and some minor-monotone graph parameters
✍ D. GonΓ§alves πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 107 KB

We study vertex partitions of graphs according to some minormonotone graph parameters. Ding et al. [J Combin Theory Ser B 79(2) (2000), 221-246] proved that some minor-monotone parameters are such that, any graph G with (G) β‰₯ 2 admits a vertex partition into two graphs with parameter at most (G)-1.

On graphs critical with respect to verte
On graphs critical with respect to vertex partition numbers
✍ Peter MihΓ³k πŸ“‚ Article πŸ“… 1981 πŸ› Elsevier Science 🌐 English βš– 362 KB

For k 3 0, pk(G) den ot e s the Lick-White vertex partition number of G. A graph G is called (n, k)-critical 'f 't I I is connected and for each edge e of G Pk (G -e) < pk (G) = n. We describe all (2, k&critical graphs and for n 23, k 2 1 we extend and simplify a result of Bollobas and Harary giving