# On vertex k-partitions of certain infinite graphs

- Authors
- Journal
- Discrete Mathematics 0012-365X
- Publisher
- Elsevier
- Publication Date
- Volume
- 23
- Issue
- 2
- Identifiers
- DOI: 10.1016/0012-365x(78)90110-3

## Abstract

Abstract Let G be an infinite graph; define deg∞ 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 on a triangular, square 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.

## There are no comments yet on this publication. Be the first to share your thoughts.